[BOJ_8394] 악수

 

📌 문제 링크: https://www.acmicpc.net/problem/8394

8394번: 악수

 

❌ 내 풀이(Failure) :

시간 초과로 틀렸던 풀이

 

✅ 내 풀이(Success) :

 

🧐 Review:

 점화식을 구하는 것은 어렵지 않았지만, 문제를 통과하기까지 코드를 몇 번이나 수정하였다. 처음 시간 초과로 문제를 틀린 이후에 코드를 수정해서 제출했지만, 계속해서 시간 초과가 발생하였다. 그래도 거의 다 풀었다는 생각에 답안을 확인하기보다 예전에 문제를 풀었을 때의 기억을 되짚어 보며 해결 방법을 생각해 보았다. 고민해 본 결과 이전에 '형변환은 생각보다 시간이 오래 걸린다'라는 글을 블로그에서 본 것 같다는 생각에 문자열로 형변환하는 과정을 거치지 않고 해결하도록 코드를 수정해 본 결과 문제를 해결할 수 있었다.

 

🚩 Idea:

 point) n의 수를 1부터 시작해서 1씩 늘려가면서 점화식을 찾는다.

   n = 1이면, 1회

   n = 2이면, 2회

   n = 3이면, 3회(1+2)

   n = 4이면, 5회(2+3)

   n = 5이면, 8회(3+5)

   n = 6이면, 13회(5+8)

 n이 5일 때 이미 점화식을 찾았지만, 혹시나 해서 6까지 확인했다. n번째 항의 값은 n-1번째 항의 값과 n-2번째 항의 값을 더해 구할 수 있다.