- 영화감독 숌 1: https://www.acmicpc.net/problem/1436
- 영화감독 숌 2: https://www.acmicpc.net/problem/27438
- 영화감독 숌 3: https://www.acmicpc.net/problem/27441
- 영화감독 숌 4: https://www.acmicpc.net/problem/27458
제약조건
- 영화감독 숌 1: N ≤ 10,000
- 영화감독 숌 2: N ≤ 13,559,699
- 영화감독 숌 3: N ≤ 10^18
풀이
DP함수
solve(len, state) 함수를 다음과 같이 정의하자
앞으로 채워야 할 자릿수가 len, 현재 자릿수 바로 앞까지 연속된 6의 갯수가 state (최대 3) 일 때, 종말의 수를 만들 수 있는 갯수
따라서, solve(len, state)을 구하기 위해서는 다음 경우들이 고려되야 할 것이다.
- 현재 자릿수에 6이 들어올 경우,
solve(len - 1, state + 1)의 경우가 한가지 - 현재 자릿수에 6이 아닌 숫자가 들어올 경우
solve(len - 1, 0)의 경우가 0~5, 7~9 로 총 9가지
즉, solve(len, state) = solve(len - 1, state + 1) + solve(len - 1, 0) * 9 이다.
코드로 표현하면 다음과 같다.
unsigned long long solve(int len, int state) {
// 666이 이미 나왔으므로 어떠한 숫자의 조합으로도 다 됨 -> 10의 len제곱
if (state == 3) return dp[len][state] = upow10(len);
if (len == 0) return 0;
if (dp[len][state] != 0) return dp[len][state];
return dp[len][state] = solve(len - 1, state + 1) + solve(len - 1, 0) * 9;
}숫자의 길이 계산
target_len이 우리가 찾고자 하는 종말의 수의 자릿수라고 하자.
solve함수를 이용하여 현재 자릿수에서 종말의 수의 갯수를 구해보자.
이번에는 다음과 같은 경우들이 고려될 것이다.
- 첫번째 자리에 6이 들어올 경우,
solve(target_len - 1, 1)의 경우가 1가지 - 첫번째 자리에 6이 아닌 숫자가 들어올 경우
solve(target_len - 1, 0)의 경우가 1~5, 7~9 로 총 8가지 (첫번째 자리이기에 0이 들어와서는 안된다.)
즉, target_len 자릿수에서 가능한 종말의 수의 개수는 solve(target_len - 1, 1) + solve(target_len - 1, 0) * 8 이 될 것이다.
N번째로 큰 종말의 수를 찾는데 만약 N보다 solve(target_len - 1, 1) + solve(target_len - 1, 0) * 8 (이를 cnt라 하자)이 작다? 그럼 그 다음 자릿수라는 거다.
그럼 target_len을 증가시키고, N-cnt번째 종말의 수를 계속 찾는거다.
이를 코드로 나타내면 다음과 같다.
int target_len = 3;
while (true) {
unsigned long long cnt = solve(target_len - 1, 0) * 8
+ solve(target_len - 1, 1);
if (N <= cnt) break;
N -= cnt;
target_len++;
}지정된 숫자의 자릿수 내에서 N번째 종말의 수 계산
최종적으로 종말의 수를 앞자리부터 한자리씩 채우는 과정이다.
현재 자릿수를 i번째 자릿수라고 하자. (헷갈림주의)
(ex. 12222 면 1은 5번째 자릿수)
STEP1
i번째 자릿수에 어떤 숫자가 들어갈 수 있을지 고려해보자.
i번째 자릿수에 들어갈 숫자를 d라 하자.
첫번째 자릿수에는 1~9의 숫자가, 두번째 자릿수부터는 0~9의 숫자가 들어갈 수 있다.
즉, i == target_len일때는 d는 1부터 9까지
i != target_len일때는 d는 0부터 9까지 들어갈 수 있다.
여하간 i번째 자릿수를 d로 채웠다고 하자. (반복문을 돌리며)
STEP2
이제, 방금 숫자의 길이 계산 단계에서 했던거랑 똑같다. 다만 정해진 자릿수에서 하나씩 채워나가는 과정이다.
이제 i-1개 자리만 마저 채우면 될 것이다.
지금 상태에서 가능한 종말의 수를 계산해서 줄여나가야 할 것이다.
- 현재 자릿수의 앞 자리까지 6이 3번 이상 반복된 경우:
solve(i - 1, 3) - 현재 자릿수의 앞자리까지 6이 3번 미만 반복된 경우:
- 현재 자릿수에서 선택된 숫자가 6일 경우:
solve(i - 1, 현재 자릿수의 앞자리까지 6이 반복된 횟수 + 1) - 현재 자릿수에서 선택된 숫자가 6이 아닐 경우:
solve(i - 1, 0)
- 현재 자릿수에서 선택된 숫자가 6일 경우:
즉, cnt = solve(i-1, curr_state == 3 ? 3 : (d == 6 ? curr_state + 1 : 0)) 이다.
N번째로 큰 종말의 수를 찾는데 만약 N보다 cnt가 작다? 그럼 그 다음 숫자라는 거다. (1이면 2,, 2면 3) 그러다가 반복문 탈출하면... 그 다음 자릿수에서 줄여나가고 그러는거다.
그럼 그 다음N-cnt번째 종말의 수를 계속 찾는거다.
int curr_state = 0;
for (int i = target_len; i >= 1; i--) {
for (int d = (i == target_len ? 1 : 0); d <= 9; d++) {
int next_state = (curr_state == 3)
? 3
: (d == 6 ? curr_state + 1 : 0);
unsigned long long cnt = solve(i - 1, next_state);
if (N <= cnt) {
cout << d;
curr_state = next_state;
break;
} else N -= cnt;
}
}숌4
27458번 영화감독 숌 4는 영화감독 숌 1,2,3번과 로직은 동일하나 입출력이 역이다.
핵심 로직은 동일하다. 패스
숌1, 2, 3 최종 완성 코드
#include <iostream>
#define MAX 20
using namespace std;
unsigned long long dp[MAX][4] = {0};
unsigned long long upow10(int n) {
unsigned long long ret = 1;
for (int i = 0; i < n; i++)
ret *= 10;
return ret;
}
unsigned long long solve(int len, int state) {
if (state == 3) return dp[len][state] = upow10(len);
if (len == 0) return 0;
if (dp[len][state] != 0) return dp[len][state];
return dp[len][state] = solve(len - 1, state + 1) + solve(len - 1, 0) * 9;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
unsigned long long N;
cin >> N;
int target_len = 3;
while (true) {
unsigned long long cnt = solve(target_len - 1, 0) * 8
+ solve(target_len - 1, 1);
if (N <= cnt) break;
N -= cnt;
target_len++;
}
int curr_state = 0;
for (int i = target_len; i >= 1; i--) {
for (int d = (i == target_len ? 1 : 0); d <= 9; d++) {
int next_state = (curr_state == 3)
? 3
: (d == 6 ? curr_state + 1 : 0);
unsigned long long cnt = solve(i - 1, next_state);
if (N <= cnt) {
cout << d;
curr_state = next_state;
break;
} else N -= cnt;
}
}
return 0;
}
숌4 최종 완성 코드
#include <iostream>
#include <string>
#define MAX 20
using namespace std;
unsigned long long dp[MAX][4] = {0};
unsigned long long upow10(int n) {
unsigned long long ret = 1;
for (int i = 0; i < n; i++)
ret *= 10;
return ret;
}
unsigned long long solve(int len, int state) {
if (state == 3) return dp[len][state] = upow10(len);
if (len == 0) return 0;
if (dp[len][state] != 0) return dp[len][state];
return dp[len][state] = solve(len - 1, state + 1) + solve(len - 1, 0) * 9;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
string target_num;
cin >> target_num;
unsigned long long target_len = target_num.length();
unsigned long long cnt = 0;
int digit_len = 3;
while (digit_len < target_len) {
cnt += solve(digit_len - 1, 0) * 8 + solve(digit_len - 1, 1);
digit_len++;
}
int curr_state = 0;
for (int i = target_len; i >= 1; i--) {
for (int d = (i == target_len ? 1 : 0); d <= 9; d++) {
int next_state = (curr_state == 3)
? 3
: (d == 6 ? curr_state + 1 : 0);
if (target_num[target_len - i] - '0' > d) {
cnt += solve(i - 1, next_state);
}
if (target_num[target_len - i] - '0' == d) {
curr_state = next_state;
break;
}
}
}
cout << cnt + 1;
return 0;
}