일정한 주기를 가지고 올라갔다 내려갔다 하는 수열에서 나머지 어쩌구 하는 문제에 대한 고뇌

먼저 아래 문제를 보자.

 

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

 

문제를 읽어보면 N이 주어질 때 N번째 외치는 수는 과연 무엇이 되어야 하는가를 구하는게 일단 어렵다.

 

 

그래서 표를 한 번 그려보았다.

주기는 (15 - 1) * 2 = 28이다.

 

그런데 28로 나눈 나머지 안에서도 절반은 증가하고 절반은 감소하기 때문에

14로 나눈 몫이 홀수인지 짝수인지에 따라 경우를 나눴다. 지금까지는.

 

이렇게 탄생한 지금까지의 나의 코드는 대충 아래와 같이 복잡하다.

 

22935번

17143번

 

매번 절편을 계산해줘야하고 보정해야해서 표를 맨날 그리기때문에 머리아프고 손아프며 시간이 걸린다.

 

그러나 아래와 같은 아주 간단한 방법이 있음을 깨달았다.

 

 

이렇게 28개씩 묶으면 사이클이 생긴다.

그래서 미리 다음과 같은 리스트를 만들어둔다.

 

[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2]

 

그 다음에 N을 28로 나눈 나머지 - 1 을 위 리스트 인덱스에 대입하면 바로 답이 나오더라. 아!