[알고리즘] 백준 2193번
문제
풀이
이 문제의 정답률은 35퍼센트였습니다! 알고리즘에 정말 약한 저에겐 넘볼 수 없는 존재 같았습니다. 하지만 정답률이 높은 문제를 찾던 도중 잘못 클릭하여 들어와서 문제를 읽어봤는데 "어? 이거 할만한데?" 라는 생각이 들었습니다. 왜냐하면 이런 비슷한 어려운 문제를 풀다가 포기를 한 적이 때문입니다...! 풀이를 보면서 코드를 하나하나 따라가도 전 풀지 못했었죠.. 그리고 그냥 포기했었던 기억이 있습니다.
근데 그때 잠깐 보았던 풀이의 원리 중 하나가 생각났습니다. 그리고 같은 원리를 적용해서 풀었더니 쉽게 풀렸습니다! 이게 알고리즘의 묘미인가 싶습니다...그냥 단순히 우연하게 기억이 났던 것일까..! 그래도 내손으로(?) 풀어서 기분은 아주 좋습니다.
제 풀이와 의식의 흐름은 다음과 같습니다.
무조건 1로 시작하겠구나 (뭐 당연한 소리)
자릿수마다 모두 작성해보았습니다.
- 3자리 - 100, 101 - 2개
- 4자리 - 1000, 1001, 1010 - 3개
- 5자리 - 1000, 1001, 10010, 10100, 10101 - 5개
여기서 하나의 규칙을 발견했습니다. 이전 맨 마지막 자릿수가 0이라면 그 뒤에는 0과 1이 붙을 수 있고, 1이라면 그 뒤에는 0만 붙을 수 있다. 왜냐하면 이친수는 1이 두 개 이상 연속으로 올 수 없기 때문입니다. 즉 3자리 이친수 중 100을 이용하여 4자리 이친수를 만들면 0, 1을 붙여 1000과 1001을 만들 수 있다. 즉 이전 자릿수 이친수들을 활용해 구하고자 하는 자릿수의 이친수의 갯수를 알 수 있는 것입니다!! 다이나믹 프로그래밍!!
이렇게 하여 만들어진 점화식은 다음과 같습니다.
- n자릿수의 이친수중 끝자리가 1인 이친수의 갯수 = n-1자릿수의 이친수중 끝자리가 0인 이친수 갯수
- n자릿수의 이친수중 끝자리가 0인 이친수의 갯수 = n-1자릿수의 이친수중 끝자리가 0인 이친수 갯수 + 1인 이친수 갯수
비슷한 풀이를 알고 있어서 그런지 저는 너무 쉽게 풀었습니다. 오히려 힘들게 풀었을 때보다 더 긴장하며 "채점중" 이라는 문구를 바라봤습니다. 하지만 "틀렸습니다!"
절망했습니다. "그래....이렇게 쉬울리가 없지..." 하지만 아무리 두 자릿수까지 직접 적어봐도 올바른 답이 나왔습니다. 그리고 90을 넣자 어라!? 이유를 알았습니다. 정수의 범위를 초과하였기 때문에 올바른 답으로 나오지 않았던 것입니다. 그래서 int로 선언해주었던 배열을 long으로 바꿨더니 "맞았습니다!!" 라는 문구를 볼 수 있었습니다.
저의 코드는 다음과 같습니다.