99클럽 코테 스터디 26일차 TIL DP(돌게임)

https://www.acmicpc.net/problem/9655

 

<아이디어>

DP문제 였는데 딱히 메모이제이션을 사용하진 않았다. 규칙을 도출하는 자체가 상향식 접근법이라고는 할 수 있겠지만..?

무튼 코드에 주석으로 정리해놓고 풀긴했지만 한번 더 정리해보면!

N을 1인 경우에서 부터 상근과 창영이 돌을 가져갈 수 있는 경우를 모두 정리해보았을 때

결국은 홀수면 상근이 이기고, 짝수면 창영이 이기는 방법밖에 없다.

따라서 N을 홀짝인 경우로 나누어 승자를 출력해주었다.

 

다만 여기서! 입력받는 값이 작아 Scanner를 사용했는데, 채점시간이 어어엄청 오래 걸리는 걸 확인했다.

그래서 BufferedReader로 바꾸어서 한번 더 해봤는데, 확실히 좀 더 빨라졌고 이 기회에 Scanner와 BufferedReader에 대해 찾아보자 맘먹었다.

 

우선, 제출했던 결과를 보면 (위가 BufferedReader 이고, 아래가 Scanner 이다)

 

Scanner

Scanner는 바이트 입력을 다양한 타입으로 파싱하여 사용하는 클래스이다.

 

BufferedReader

BufferedReader는 데이터를 한번에 읽어와 버퍼에 보관한 후, 버퍼에서 필요한 데이터를 파싱하지 않고 String으로 읽어오는 클래스이다.

 

즉, 문자가 입력 될 때마다 CPU가 하나씩 입출력을 하는 Scanner보다 버퍼에 쌓아두고 가득차거나 개행시 입출력을 처리하는 BufferedReader가 메모리는 조금 더 사용할지라도 속도면에서 훨 빠르다는 것이다! (실제로 백준에서 제공하는 입력속도 비교표를 보면 Scanner는 4.8448초 이고, BufferedReader는 0.68585초 라고 한다.)

 

<제출코드>

package Study.Week04;

/*
* N = 1  상근1 SK
* N = 2  상근1 창영1 CY
* N = 3  상근3 SK
* N = 4  상근1 창영3 CY / 상근3 창영1 CY
* N = 5  상근1 창영3 상근1 / 상근1 창영1 상근3 / 상근3 창영1 상근1 SK
*
* => N이 홀수면 상근이 이기고, N이 짝수면 창영이 이김
* */

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Day26_BOJ_9655_돌게임 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        if(n % 2 == 1) System.out.println("SK");
        else System.out.println("CY");
    }
}