반응형

https://www.acmicpc.net/problem/2591

 

2591번: 숫자카드

1부터 34까지 수가 적힌 카드가 충분히 많이 있다. 이들 중 몇 장을 일렬로 늘어놓고, 그 숫자를 차례로 적었다. 예를 들어 아래와 같이 카드가 놓인 경우 숫자를 차례로 적으면 27123이 된다. 나중

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. 차례로 적어 놓은 숫자를 저장하고, 점화식을 이용하여 문제를 풉니다.

 

2. 만약 str[ i ] 가 0이라면 ans[ i - 1 ] = 0, ans[ i ] = ans[ i - 2 ]의 식을 사용합니다.

 

3. 만약 str[ i - 1 ]과 str[ i ]의 숫자를 조합했을 때 34보다 작거나 같다면 ans[ i ] = ans[ i - 1 ] + ans [ i - 2 ]의 식을 사용하고, 그렇지 않다면 ans[ i ] = ans [ i - 1]의 식을 사용합니다.

 

4. ans[ str.size() - 1 ]을 출력합니다.

 

[ 소스코드 ]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include<iostream>
#include<string>
 
using namespace std;
 
int ans[40];
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    string str;
 
    cin >> str;
 
    ans[0] = 1;
    if (str[1] - '0' == 0) {
        ans[1] = 1;
        ans[0] = 0;
    }
    else {
        if ((str[0] - '0') * 10 + str[1] - '0' <= 34) {
            ans[1] = 2;
        }
        else {
            ans[1] = 1;
        }
    }
 
    for (int i = 2; i < str.size(); i++) {
        if (str[i] - '0' == 0) {
            ans[i] = ans[i - 2];
            ans[i - 1] = 0;
        }
        else {
            if ((str[i - 1] - '0') * 10 + str[i] - '0' <= 34) {
                ans[i] = ans[i - 2] + ans[i - 1];
            }
            else {
                ans[i] = ans[i - 1];
            }
        }
    }
 
    cout << ans[str.size() - 1];
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

'백준' 카테고리의 다른 글

[ 백준 ] 2463번 - 비용 (C++)  (0) 2023.08.23
[ 백준 ] 2479번 - 경로 찾기 (C++)  (0) 2023.08.22
[ 백준 ] 2116번 - 주사위 쌓기 (C++)  (0) 2023.08.20
[ 백준 ] 10216번 - Count Circle Groups (C++)  (0) 2023.08.19
[ 백준 ] 3067번 - Coins (C++)  (0) 2023.08.18

+ Recent posts

티스토리툴바