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차 배열로 축소시켜서 문제를 풀어도 된다.
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <stdio.h> | |
int main() | |
{ | |
int n; | |
long long dp[91] = { 0, }; | |
dp[1] = 1; dp[2] = 1; | |
scanf("%d", &n); | |
for (int i = 3; i <= n; i++) { | |
dp[i] = dp[i - 1] + dp[i - 2]; | |
} | |
printf("%lld\n", dp[n]); | |
return 0; | |
} |

(ETS2 하려고 다운로드하고 있는데 너무 느려서 기다리는 동안 푼 문제라 기분이 더 좋다 ㅎ)
'온라인저지' 카테고리의 다른 글
[BOJ]2606번: 바이러스 (0) | 2018.02.05 |
---|---|
[BOJ] 1932번: 숫자삼각형 (0) | 2018.02.03 |
[BOJ]1978번: 소수 찾기 (0) | 2018.02.02 |
[BOJ]2669번: 직사각형 네개의 합집합의 면적 구하기 (0) | 2018.01.25 |
[BOJ]2667번: 단지번호붙이기 (0) | 2018.01.25 |
[BOJ] 1002번 : 터렛 (0) | 2017.11.16 |