[BOJ]2193번: 이친수

문제 풀러 가기

2193번: 이친수

처음에는 문제를 잘못 보고 n이 주어졌을 때 n을 이진수로 바꿔서 이친수인지 확인하는 문제인줄 알았다. 이래서 문제를 잘 읽어야 한다;;

 

어쨋거나 이 문제는 DP문제인데 처음에는 왜 DP인가 했지만 주어진 조건들을 보고 손으로 하다보니 DP라는 사실을 알게 되었다.

맨 끝자리가 0으로 끝나면 파생될 수 있는 숫자가 '0'과 '1'로 두 개이고 1로 끝나면 '0'으로 파생된다.

규칙은 찾았고 분명히 개수에도 규칙이 있을 것 같아 몇 개 적은 것을 보니깐 피보나치 수열이라는 사실을 알았다.

 

아! 그리고 참고로 처음에 제출했을 때 틀려서 질문 올라온 것을 보니깐 90자리까지 나올 수 있는데 그러면 long long이 필요할 것 같아서 고쳤더니 맞았다.

 

+ 추가: 2020/07/22)

다시 풀어보니 다른 방식으로 점화식을 세워서 블로그에 추가해보려고 한다. 참고로 다시 풀 때는 이 문제가 피보나치로 나온다는 생각을 못했다; 아무튼 다음과 같이 점화식을 세울 수 있다.

 

DP[i][j]: 길이가 i이면서 j로 끝나는 이친수의 개수

DP[i][0] = DP[i][1] + DP[i][0], DP[i][1] = DP[i][0]

 

이렇게 하면 똑같은 답을 구할 수 있다. 그런데 이 접근에서 어떻게 피보나치까지 생각을 확장할 수 있을까? 나는 이에 대한 모든 정보를 질문 게시판에서 얻었음을 미리 밝힌다.

DP[i][0]를 Fi로, DP[i][1] Gi로 두면, Fi = F(i-1) + G(i-1)와 Gi=F(i-1)로 표현할 수 있다. 그 다음에는 Gi의 정의를 좀 더 응용하면 된다. G(i-1)는 F(i-2)로 정의될 수 있겠다. 그래서 Fi의 표현식에 있는 G(i-1)와 치환하면 된다. 그러면 최종적으로 다음과 같은 식이 나온다.

 

Fi = F(i-1) + F(i-2)

 

DP[i][0] = DP[i-1][0] + DP[i-2][0]로 계산해도 되지만 이런 상태에서는 DP[i][1]는 전혀 사용하지 않기 때문에 1차 배열로 축소시켜서 문제를 풀어도 된다.

 

 

 

(ETS2 하려고 다운로드하고 있는데 너무 느려서 기다리는 동안 푼 문제라 기분이 더 좋다 ㅎ)