문제
1부터 34까지 수가 적힌 카드가 충분히 많이 있다. 이들 중 몇 장을 일렬로 늘어놓고, 그 숫자를 차례로 적었다. 예를 들어 아래와 같이 카드가 놓인 경우 숫자를 차례로 적으면 27123이 된다.
![](https://blog.kakaocdn.net/dn/b1oB6e/btsrxPZngzu/0Q1jJn4RmzULkhj7CYATv1/img.png)
나중에, 적어 놓은 것에 맞게 다시 카드를 늘어놓으려고 보니, 방법이 여러 가지일 수 있다는 것을 알았다. 예를 들어 27123의 경우 아래와 같이 여섯 가지 다른 방법이 있다.
![](https://blog.kakaocdn.net/dn/n2err/btsrCTM11IP/cD9RKpKk9y52WUBzNRD8Lk/img.png)
카드의 숫자를 차례로 적어 놓은 것이 주어질 때, 위와 같이 그것을 가지고 거꾸로 카드의 배열을 찾으려고 한다. 가능한 카드의 배열이 모두 몇 개인지 구하는 프로그램을 작성하시오.
입력
첫 줄에 카드의 숫자를 차례로 적어 놓은 것이 주어지며, 이것은 최대 40자 이하의 숫자로 이루어진다.
출력
첫 줄에 가능한 카드 배열이 몇 개인지를 출력한다.
Solved.ac 레벨
골드 V
풀이
간만에 머리가 빙글빙글 돌아가서 어지러웠던 문제.
DP 뇌는 언제쯤 활성화가 될까.
- 문자열로 수열을 입력받음 (str)
- dp[i]는 수열 0 ~ i - 1번째까지의 수를 숫자카드로 만드는 경우의 수
- dp[0] = 1, dp[1] = 1로 초기화. (1개의 수열을 숫자카드로 만드는 경우의 수는 1가지 밖에 없음.)
- dp[2], 두 자리 수를 숫자카드로 만드는 경우의 수부터 탐색.
* 예제에서는 숫자 0이 포함되지 않아 예제만으로 보면 헷갈릴 가능성이 있었다.
예제 27123을 토대로 과정을 풀이해본다.
1. dp[1]
'2'를 숫자카드로 만드는 경우.
위에서 기술했던대로 1가지 뿐이므로 1로 초기화
2. dp[2]
'27'을 숫자카드로 만드는 경우.
2 - 1.
먼저 현재 str의 자리, str[1]부터 생각해본다. (문자열의 인덱스이기 때문에 -1)
str[1]은 7이며, 0이 아니므로 각각 숫자카드 1장으로 만들 수 있는 경우의 수, 즉 dp[1]의 경우의 수로 초기화를 해준다.
-> dp[2] = dp[1] => 1
2 - 2.
다음으로는 두 자리 수가 34 이하여서 한 장의 카드로 구현이 가능한지 생각해본다.
str[0] * 10 + str[1] = 27 이 34이하이면서, str[0]이 0이 아니기 때문에 한 장의 카드로 구현이 가능하다.
str[0]이 0이라면 02, 07 같은 두 자리 숫자가 34 이하임을 만족시킬 수 있으며, 0 카드는 존재하지 않기 때문이다.
이는 0장의 카드를 만드는 경우의 수에 27 카드 1장을 사용하는 경우의 수를 더해주면 된다.
-> dp[2] += dp[0] => 1 + 1 = > 2
3. dp[3]
'271'을 숫자카드로 만드는 경우.
3 - 1.
2 - 1과 마찬가지로 현재 str의 자리, str[2]부터 생각해보자.
str[2]는 1이며, 0이 아니므로 각각의 숫자카드 1장으로 '27'까지 만드는 경우의 수, 즉 dp[2]의 경우의 수로 초기화를 해준다.
-> dp[3] = dp[2] => 2
3 - 2.
다음으로는 두 자리 수가 34 이하인지 판단해본다.
str[1] * 10 + str[2] = 71이 34를 초과하므로 한 장의 카드로 구현할 수 없다.
따라서 27을 한 장의 카드로 만드는 경우 1가지만 존재하므로 dp[3]에는 더 이상의 변화는 존재하지 않는다.
4. dp[4]
'2712'를 숫자카드로 만드는 경우.
4 - 1.
현재 str의 자리 str[3]은 2, 0이 아니므로 각각의 숫자카드 1장으로 271까지 만드는 경우의 수, 즉 dp[3]의 경우의 수로 초기화를 해준다.
-> dp[4] = dp[3] => 2
4 - 2.
다음으로 다시 두 자리 수가 34 이하인지 판단.
str[2] * 10 + str[3] = 12이 34 이하이므로 한 장의 카드로 구현할 수 있다.
따라서 '27' 까지를 만드는 경우 + '12'를 만드는 경우를 추가해준다.
dp[4] += dp[2] => 2 + 2 = 4
5. dp[5]
'27123'을 숫자카드로 만드는 경우.
5 - 1.
현재 str의 자리 str[4]는 3, 0이 아니므로 각각의 숫자카드로 2712까지 만드는 경우의 수, 즉 dp[4]의 경우의 수로 초기화한다.
-> dp[5] = dp[4] => 4
5 - 2.
다음으로 다시 또 두 자리 수가 34 이하인지 판단.
str[3] * 10 + str[4] = 23이 34 이하이므로 한 장의 카드로 구현 가능.
따라서 '271' 까지를 만드는 경우 + '23'을 만드는 경우 추가
dp[5] += dp[3] => 4 + 2 = 6
따라서 답은 6이 되고, 점화식은 아래와 같다.
1. 현재 탐색 중인 문자열의 자리( i - 1) 가 0이 아닐 때
dp[i] = dp[i - 1]
2. 현재 탐색 중인 문자열의 자리와 그 앞의 자리를 이용해 2자리 수를 만들었을 때 34 이하이며 이전의 수가 0이 아닐 때
dp[i] += dp[i - 1]
Code
#include<bits/stdc++.h>
using namespace std;
int dp[41];
string str;
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> str;
int ans = str.length();
//문자열의 길이 저장.
dp[0] = 1;
dp[1] = 1;
//1로 초기화
for(int i = 2; i <= ans; i++) {
if(str[i - 1] != '0') {
dp[i] = dp[i - 1];
}
if(((str[i - 2] - '0') * 10) + (str[i - 1] - '0') <= 34 && str[i - 2] != '0') {
dp[i] += dp[i - 2];
}
}
cout << dp[ans] << "\n";
return 0;
}
2591번: 숫자카드
1부터 34까지 수가 적힌 카드가 충분히 많이 있다. 이들 중 몇 장을 일렬로 늘어놓고, 그 숫자를 차례로 적었다. 예를 들어 아래와 같이 카드가 놓인 경우 숫자를 차례로 적으면 27123이 된다. 나중
www.acmicpc.net
'Study (etc) > Problem Solving' 카테고리의 다른 글
[BOJ / C++] 17836번 : 공주님을 구해라! (0) | 2023.08.19 |
---|---|
[BOJ / C++] 6593번 : 상범 빌딩 (0) | 2023.08.18 |
[BOJ / C++] 1245번 : 농장 관리 (0) | 2023.08.16 |
[BOJ / C++] 5582번 : 공통 부분 문자열 (0) | 2023.08.10 |
[BOJ / C++] 2589번 : 보물섬 (0) | 2023.08.10 |