더 이상 tistory 블로그를 운영하지 않습니다. glanceyes.github.io에서 새롭게 시작합니다.

새소식

알고리즘/BOJ 풀이

BOJ 백준 2201번 이친수 찾기

  • -

 

 

BOJ 백준 2201번 이친수 찾기

 

문제: https://www.acmicpc.net/problem/2201

 

2201번: 이친수 찾기

0과 1로만 이루어진 수를 이진수라 한다. 이러한 이진수 들 특별한 성질을 갖는 것들이 있는데, 이들을 이친수(pinary number)라 한다. 이친수는 다음의 성질을 만족한다. 이친수는 0으로 시작하지 않

www.acmicpc.net

 

이진수 중에서 다음과 같은 성질을 만족하는 것들을 이친수라고 하자.

1. 이친수는 0으로 시작하지 않는다.

2. 이친수에서는 1이 두 번 연속으로 니타나지 않는다.

이와 같은 이친수를 이진수의 크기 순서대로 정렬하여 차례로 번호를 붙였을 때, K번째 이친수를 찾아야 한다.

 

우선 각 자리 수마다 이친수가 몇 개 존재하는지를 구해서 K번째 이친수를 찾을 때 자리 수를 활용하고자 한다. 각 자리 수마다의 이친수 개수는 동적 프로그래밍(Dynamic Programming)을 사용해서 구할 수 있다.

 

 

D[N][0]: 길이(자리 수)가 N이고 마지막 숫자가 0인 이친수 개수

D[N][1]: 길이(자리 수)가 N이고 마지막 숫자가 1인 이친수 개수

 

 

자리 수가 N-1인 이친수의 끝에 0을 추가해서 자리 수가 N인 이친수를 만드는 경우, N-1 자리의 이친수의 끝자리는 0이든 1이든 상관 없다. 0은 이친수의 첫 자리에만 오지 않는다면 어떠한 이친수 끝에 붙어도 되어서다. 그러나 N-1 자리의 이친수 끝 자리 숫자가 1인 경우, 1이 두 번 연속으로 나타나지 않아야 되는 이친수의 조건을 만족해야 하므로 뒤에 0만 추가할 수 있다. 이를 정리하면 다음과 같다.

 

 

D[N][0] = D[N-1][0] + D[N-1][1]

D[N][1] = D[N-1][0]

 

 

D[1][0] = 0 D[1][1] = 1 가장 큰 수: 1
D[2][0] = 1 D[2][1] = 0 가장 큰 수: 10
D[3][0] = 1 D[3][1] = 1 가장 큰 수: 101
D[4][0] = 2 D[4][1] = 1 가장 큰 수: 1010

 

 

여기서는 2차원 배열을 사용하여 N 자리의 이친수 개수를 구했지만, 사실 굳이 2차원 배열이 아니라 1차원 배열을 사용해서 이친수 개수를 저장해도 된다. N 자리의 이친수를 만드는 것은 N-1 자리 이친수에 숫자 0 하나를 추거하는 경우에다가 N-2 자리 이친수에 두 자리 "01"을 추가하는 경우를 더한 것과 같기 때문이다. 필기 노트의 '참고' 부분을 보면 자세히 알 수 있다.

 

 

D[N] = D[N-1] + D[N-2]

 

 

단순히 각 자리 수마다의 이친수 개수만 구했다고 해서 K번째의 이친수를 찾을 수는 없다. K라는 서수는 앞에서 누적되어 온 수여서다. 따라서 가장 작은 이친수부터 N 자리 이친수 중 가장 큰 수까지 몇 개의 이친수가 있는지 아는 것이 문제의 목표를 찾는 데 있어서 key가 된다.

 

SUM[N]: 길이(자리 수)가 N인 이친수 중에서 가장 큰 수가 전체 이친수에서 몇 번째인가?

 

가장 작은 이친수부터 N자리 이친수의 가장 큰 수까지 이친수 총 개수는 N-1자리 가장 큰 이친수까지의 개수에 N 자리 이친수 개수를 더한 값이다.

 

 

SUM[N] = SUM[N-1] + D[N][0] + D[N][1]

 

 

D[1][0] = 0 D[1][1] = 1 가장 큰 수: 1 SUM[1] = 1
D[2][0] = 1 D[2][1] = 0 가장 큰 수: 10 SUM[2] = 2
D[3][0] = 1 D[3][1] = 1 가장 큰 수: 101 SUM[3] = 4
D[4][0] = 2 D[4][1] = 1 가장 큰 수: 1010 SUM[4] = 7

 

그러면 K번째 이친수가 어떠한 자리 수를 지니는지 SUM 배열 값을 통해 알 수 있고, 가장 앞 자리 숫자를 제외한 나머지 자리의 이친수 개수를 참고하여 앞 자리부터 가능한 숫자를 차례로 채워나간다.

 

현재 보고 있는 이친수 A가 K번째 이친수이고, A의 자리 수를 N이라고 하자.

 

1) K번째 이친수에서 K가 N-1 자리 이친수 개수보다 작거나 같으면

⇒ 이친수 A는 N-1 이하의 자리 수를 가지므로 맨 앞 숫자로 0이 온다.

 

2) K번째 이친수에서 K가 N-1 자리 이친수 개수보다 크면

⇒ 이친수 A는 N 자리 이친수이므로 맨 앞의 두 숫자로 "10"이 온다.

⇒ 새로 붙인 숫자들을 제외한 뒷부분에 관해 이를 계속 실행하므로 A는 새로 붙인 "10"의 뒷부분이 되고 이에 따라 서수 K 값도 앞에서 숫자를 붙인 그 뒷부분에 해당되는 것으로 대응하여 바뀐다.

 

#include <cstdio> using namespace std; const int L_MAX = 100; long long k; long long dp[L_MAX + 1][2]; long long sum[L_MAX + 1]; int main(){ scanf("%lld", &k); dp[1][1] = 1; sum[1] = 1; for (int i = 2; i <= L_MAX; i++){ dp[i][0] = dp[i - 1][0] + dp[i - 1][1]; dp[i][1] = dp[i - 1][0]; sum[i] = dp[i][0] + dp[i][1] + sum[i - 1]; } if (k == 1){ printf("1\n"); } else { printf("1"); int n = 0; for (int i = 2; i <= L_MAX; i++){ if (k <= sum[i]) { n = i; break; } } k -= (sum[n - 1] + 1); n -= 1; while (n > 0) { if (k > sum[n - 1]){ printf("1"); k -= (sum[n - 1] + 1); } else { printf("0"); } n -= 1; } printf("\n"); } return 0; }

 

Contents

글 주소를 복사했습니다

부족한 글 끝까지 읽어주셔서 감사합니다.
보충할 내용이 있으면 언제든지 댓글 남겨주세요.