문제 정보
플랫폼 : 백준
분류 : 동적 프로그래밍 (DP)
난이도 : 실버4
링크 : https://www.acmicpc.net/problem/9656
풀이
DP문제를 풀 때는 표를 그려보는 것이 도움이 많이 된다고 생각한다. DP문제를 얼마나 잘 푸는지는 표를 얼마나 잘 그리고, 어떻게 접근해야 할지(점화식 세우기)에 대해 잘 아는 것이라고 생각한다.
n = 1
상근(1) > 상근이 가져가야 하므로 창영이 이긴다.
n = 2
상근(1) > 창영(1)
상근이 가져간 뒤, 창영이 가져가야 하므로 상근이 이긴다.
n = 3
두 가지의 경우가 존재한다.
상근(1) > 창영(1) > 상근(1)
상근(3)
1. 처음부터 상근이 3개를 가져가는 경우
2. n=2에서 다음 차례인 상근이 가져가는 경우.
모두 상근이 패배하는 경우이다. 따라서 창영의 승리
n = 4
두 가지의 경우가 존재한다.
1. 상근(1) > 창영(3)
2. 상근(3) > 창영(1)
(참고) 상근(1) > 창영(1) > 상근(1) > 창영(1)의 경우 2번과 같은 로직이다.
어차피 뭘 해도 창영이 진다. 상근의 승리.
...
경우의 수를 생각해보면,
F(n) = F(n-1) + 하나를 뽑는 경우
F(n) = F(n-3) + 하나를 뽑는 경우로 정리할 수 있다.
따라서 이런 표가 만들어질 수 있다. 일반화 시키면, n % 2 == 0인 경우 SK(상근)을 출력하고, n % 2 == 1인 경우 CY(창영)를 출력하면 된다.
코드
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
if(n % 2 == 0)
System.out.println("SK");
else
System.out.println("CY");
}
}개인적인 의견
굉장히 쉬운 문제이다. 실버4가 아까운..? 문제이다. 이러한 간단한 문제로 점화식을 찾아내는 방법을 유도해보는 연습을 하는것도 좋다.
더 많은 정답 코드
블로그를 쓰기 이전에 풀어본 문제들이 많다. 해설강의는 없지만, 백준 문제의 풀이 코드가 필요한 경우 이곳을 클릭하여 소스코드를 참조해보도록 하자. 단, 코드만 복사-붙여넣기 하는것은 본인에게 결코 도움이 되지 않는다. 반드시 먼저 생각해보고, 막히는 경우에 참고하고 왜 이렇게 코드가 작성됐는지를 다시 한 번 생각해보는 습관을 들이자.
