[백준] 9655번 돌 게임 JAVA (자바) 풀이

문제 9655번 (수학, DP)

 : 탁자 위에 돌 N개

   상근이와 창영이는 턴을 번갈아가면서 돌은 1개 또는 3개 가져갈 수 있다

   마지막 돌을 가져가는 사람이 게임을 이기게 된다

   게임은 상근이가 먼저 시작한다.

 

 

[입력]

 :  첫째 줄에 N (1 ≤ N ≤ 1000)

 

 

[출력]

 :  상근이가 이기면 SK를, 창영이가 이기면 CY을 출력

 

[설명]

 

DP 알고리즘

: 이미 계산된 결과는 별도의 메모리 영역에 저장하여 다시 계산하지 않음으로서 수행 시간 단축시키는 방법

  DP 구현 방법은 일반적으로 Top-down(하향식)과 Bottom-up(상향식)으로 구성된다

 

탑다운 (Top-Down)	보텀업 (Bottom-Up)
작은 크기로 문제를 나눠서 해결	작은 것부터 해결해서 점차 빌드업
메모제이션 (memoization)	타뷸레이션 (tabulation)
일부만 계산해도 답이 나올 때	모두 계산해야 답이 나올 때
재귀	반복문
시간 복잡도 O(n)	시간 복잡도 O(n)

 

1. N이 홀수면 상근이 짝수면 찬영이 규칙!

 

 

 [코드]

import java.io.*;
import java.util.*;
public class Main{
    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");
    }
}

 

 

 [해설]
     

 :  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");

 

 

 

 

 

 

이제 풀어보러 갈께요 :)

 

 

 

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

 

 

 

 

* 독학으로 익히는 코딩이라 틀린 것이 있을 수 있습니다. 오류가 있다면 댓글을 통해 알려주세요. 감사합니다. *