BOJ 3999

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

 

코드

http://boj.kr/c617274fbc344cd39f524bd87344d40c

 

ICPC Northern Eurasia Finals NEERC 2012 J

 

난이도 : P1

 

Elapse Time : 50min

 

문제를 보고 #2301과 비슷하다는 생각은 했는데 점프의 거리가 1, 2, 3만으로 이루어져 있다는 것이 풀이를 떠올리기 힘들게 만들었다. 처음에는 0 3 2 1 4와 같은 단위 움직임을 여러 개 만들어 놓고 주어진 $a$, $b$, $c$에 따라 단위 움직임들을 조합하여 풀 생각을 했으나 단위 움직임을 몇 개 만들어서 조합해도 만들어지지 않는 극단적인 조합들이 존재했다. 그래서 다른 접근의 필요성이 느껴졌고 1짜리는 혼자 있어도 모두 소모할 수 있으므로 2와 3을 모두 소모시킬 생각을 했다. 2의 경우 1 하나만 있어도 갔다가 되돌아오면서 모두 소모할 수 있기 때문에 3을 소모시키는 데 집중했다. 그러다가 $c$를 3으로 나눈 나머지에 따라 움직이는 방법을 설정해 주면 1, 2 중 한두 개를 사용하여 3을 모두 소모시킬 수 있음을 알게 되었고 $c$를 3으로 나눈 나머지에 따라 casework를 해주어 풀었다.