반응형

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

 

17404번: RGB거리 2

첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나

www.acmicpc.net

 

 

[ 문제풀이 ]

 

https://rudalsd.tistory.com/12

 

[ 백준 ] 1149번 - RGB거리 (C++)

https://www.acmicpc.net/problem/1149 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주..

rudalsd.tistory.com

위 글을 먼저 보고 오는 것을 추천드립니다!!

 

일반 RGB거리와 다른 점은 1번 집과 N번 집도 색깔이 같으면 안 된다는 조건입니다.

 

따라서 일반적인 RGB거리의 답을 구하는 방식으로 구하되 마지막에 1번 집과 N번 집이 같지 않을 때의 최솟값을 구하면 되는 문제입니다.

 

[ 소스 코드 ]

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
#define MAX 987654321
 
#include <iostream>
 
using namespace std;
 
int N;
 
int arr[3][1001];        //각 색의 가격을 저장할 배열
int dp[3][1001];        //각 색을 칠했을 때의 총 가격
 
int main()
{
    cin >> N;
    int ans = MAX;
    for (int i = 1; i <= N; i++) {
        cin >> arr[0][i] >> arr[1][i] >> arr[2][i];
    }
 
    for (int i = 0; i < 3; i++)    //첫 집의 색깔을 졍해주기
    {
        for (int j = 0; j < 3; j++) {
            if (i == j) dp[j][1] = arr[j][1];    //첫 집의 색만 가격 입력
            else dp[j][1] = MAX;                //나머지 색은 가격 MAX
        }                                        //다음 집에서 첫 집의 색을 고르지 못하도록 하기 위해서
 
        for (int j = 2; j <= N; j++) {
            dp[0][j] = min(dp[1][j - 1], dp[2][j - 1]) + arr[0][j];    //앞의 집의 색 중 가격이 싼 색의 값과 지금 집 색의 값을 더함
            dp[1][j] = min(dp[0][j - 1], dp[2][j - 1]) + arr[1][j];
            dp[2][j] = min(dp[0][j - 1], dp[1][j - 1]) + arr[2][j];
        }
 
        for (int j = 0; j < 3; j++) {
            if (i != j) {                //마지막 집이 첫 집과 색이 같으면 안되기 때문에 i!=j 조건 넣기
                ans = min(ans, dp[j][N]);
            }
        }
    }
 
    cout << ans;
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 9328번 - 열쇠 (C++)  (0) 2022.06.20
[ 백준 ] 1167번 - 트리의 지름 (C++)  (0) 2022.06.19
[ 백준 ] 7662번 - 이중 우선순위 큐 (C++)  (0) 2022.06.17
[ 백준 ] 1967번 - 트리의 지름 (C++)  (0) 2022.06.16
[ 백준 ] 13549번 - 숨바꼭질 3 (C++)  (0) 2022.06.15
반응형

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

 

13549번: 숨바꼭질 3

수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일

www.acmicpc.net

 

 

[ 문제풀이 ]

 

dp를 이용해서 풀 수 있는 문제였습니다.

 

이동할 수 있는 방법은 -1, 1, *2 총 3개였습니다. 이때 *2로 이동할 때는 시간이 0의 시간이 걸리고, 나머지 이동 중에는 1의 시간이 걸립니다.

 

그렇다면 N보다 작거나 같은 칸으로 이동할 때는 무조건 한 칸에 1씩 걸리므로 dp [ i ] = N - i 가 됩니다.

 

나머지 경우에는 i가 짝수일 때 dp[ i + 1 ] + 1, dp [ i - 1 ] + 1, dp [ i / 2 ] 중 가장 작은 값을 선택하면 되고, 홀수일 때는 dp [ i + 1 ] + 1, dp [ i - 1 ] + 1 중 가장 작은 값을 선택하면 됩니다.

 

또한 순간이동 시 이동시간이 2이므로 각 노드에 도착했을 때 *2로 이동할 수 있는 모든 칸에 대하여 dp [ cur ] < dp [ next ] 일 경우에 dp [ next ] = dp [ cur ]로 바꿔주면 됩니다.

 

마지막으로 dp[ K ]를 출력합니다.

 

[ 소스 코드 ]

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>
 
using namespace std;
 
int N, K;
int dp[200001];
 
void tel(int num)
{
    int cur = num;
    while (1) {
        num *= 2;
        if (num > 200001) {
            break;
        }
        if (dp[num] > dp[cur]) {
            dp[num] = dp[cur];
        }
    }
}
 
int main()
{
    cin >> N >> K;
 
    for (int i = 0; i < 200001; i++) {
        dp[i] = 987654321;
    }
 
    for (int i = 0; i < 200001; i++) {
        if (i <= N) {
            dp[i] = N - i;
        }
        else {
            if (i % 2 == 0) {
                dp[i] = min(min(dp[i - 1] + 1, dp[i + 1] + 1), dp[i / 2]);
            }
            else {
                dp[i] = min(dp[i - 1] + 1, dp[i + 1] + 1);
            }
        }
        if (i > 0) {
            tel(i);
        }
    }
 
    cout << dp[K];
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 7662번 - 이중 우선순위 큐 (C++)  (0) 2022.06.17
[ 백준 ] 1967번 - 트리의 지름 (C++)  (0) 2022.06.16
[ 백준 ] 9935번 - 문자열 폭발 (C++)  (0) 2022.06.14
[ 백준 ] 2638번 - 치즈 (C++)  (0) 2022.06.13
[ 백준 ] 13460번 - 구슬 탈출 2 (C++)  (0) 2022.06.12
반응형

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

 

12865번: 평범한 배낭

첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000)

www.acmicpc.net

 

 

[ 문제풀이 ]

 

dp문제 중에 쉬운 편에 속하고, 매우 직관적인 문제입니다.

 

2차원 배열을 만들고 각 행과 열에 i번째 물건까지 넣을 수 있고, 배낭에 넣을 수 있는 최대 무게가 j일 때, 최댓값을 경신해나가면 dp [ N ][ K ]가 배낭에 넣을 수 있는 최댓값이 됩니다.

 

예제를 예로 들면 물건들의 정보는 다음과 같습니다.

 

 

다음 2차원 배열에서 i 는 물건의 개수를 의미하고, j는 가방의 무게를 의미합니다.

 

먼저 i가 1일 때 가방의 무게가 최소 6일 때 물건을 담을 수 있습니다. 따라서 표를 채우면 다음과 같은 결과를 얻을 수 있습니다.

 

 

그리고 i가 2일 때 표는 다음과 같습니다.

 

 

그리고 문제의 핵심 부분인 i가 3일 때 표입니다.

 

 

무게가 7일 때 dp[dp [ 3 ][ 7 ] = dp [ 3 - 1 ][ 7 - 3 ] + 6로 경신되는 것을 볼 수 있습니다. 가방의 무게가 7일 때 지금까지는 최댓값이 13이었지만 위의 결과를 통해 14로 경신되었습니다. 이와 같이 점화식을 세워보면 다음과 같습니다.

 

dp [ i ][ j ] = max( dp [ i - 1 ][ j - W] + V, dp [ i - 1 ][ j ] )

 

표를 마지막까지 채워보면,

 

 

위와 같은 결과를 얻을 수 있고, 결과적으로 dp[ N ][ K ]를 출력해주면 됩니다.

 

 

[ 소스 코드 ]

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
#include <iostream>
 
using namespace std;
 
struct stuff {
    int W;
    int V;
};
 
int N, K;
stuff arr[101];
int dp[101][100001];
 
int main()
{
    cin >> N >> K;
 
    for (int i = 1; i <= N; i++) {
        cin >> arr[i].W >> arr[i].V;
    }
 
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= K; j++) {
            if (j >= arr[i].W) {
                dp[i][j] = max(dp[i - 1][j - arr[i].W] + arr[i].V, dp[i - 1][j]);
            }
            else {
                dp[i][j] = dp[i - 1][j];
            }
        }
    }
 
    cout << dp[N][K];
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 1865번 - 웜홀 (C++)  (0) 2022.06.10
[ 백준 ] 1238번 - 파티 (C++)  (0) 2022.06.09
[ 백준 ] 9663번 - N-Queen (C++)  (0) 2022.06.07
[ 백준 ] 1504번 - 특정한 최단 경로 (C++)  (0) 2022.06.06
[ 백준 ] 11054번 - 가장 긴 바이토닉 부분 수열 (C++)  (0) 2022.06.05
반응형

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

 

11054번: 가장 긴 바이토닉 부분 수열

첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000)

www.acmicpc.net

 

 

[ 문제풀이 ]

 

가장 긴 증가하는 부분 수열을 구하는 문제를 풀어보고 풀어보시기를 추천드립니다!

 

먼저 각 idx의 증가하는 부분 수열 길이의 최댓값을 increase 배열에 lower_bound를 활용하여 저장해줍니다. 마찬가지로 감소하는 부분 수열은 배열의 끝부분에서부터 시작하여 부분 수열 길이의 최댓값을 decrease 배열에 lower_bound를 활용하여 저장해줍니다.

 

다음으로 0번째 idx부터 N-1번째 idx까지 increase 배열과 decrease 배열을 더한 값에 -1을 해준 후 최댓값을 max에 저장해준 뒤 출력하면 답을 쉽게 구할 수 있습니다.

 

-1을 해주는 이유는 특정 idx에서 increase 배열과 decrease 배열이 한번 겹치기 때문입니다.

 

 

[ 소스 코드 ]

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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
#include <iostream>
#include <algorithm>
#include <vector>
 
using namespace std;
 
int arr[1000];
int increase[1000];
int decrease[1000];
vector<int> mem;
 
int N;
 
int main()
{
    cin >> N;
 
    for (int i = 0; i < N; i++) {
        scanf("%d", &arr[i]);
    }
 
    int max = 1;
 
    for (int i = 0; i < N; i++) {        //증가하는 부분 수열의 최대 길이 increase에 저장
        if (i == 0) {
            mem.push_back(arr[i]);
        }
        else {
            if (mem[mem.size() - 1] < arr[i]) {
                max++;
                mem.push_back(arr[i]);
            }
            else {
                int idx = lower_bound(mem.begin(), mem.end(), arr[i]) - mem.begin();
                mem[idx] = arr[i];
            }
        }
        increase[i] = max;
    }
 
    max = 1;
    mem.clear();
 
    for (int i = N-1; i >= 0; i--) {    //감소하는 부분 수열의 최대 길이 decrease에 저장
        if (i == N-1) {
            mem.push_back(arr[i]);
        }
        else {
            if (mem[mem.size() - 1] < arr[i]) {
                max++;
                mem.push_back(arr[i]);
            }
            else {
                int idx = lower_bound(mem.begin(), mem.end(), arr[i]) - mem.begin();
                mem[idx] = arr[i];
            }
        }
        decrease[i] = max;
    }
 
    max = 0;
 
    for (int i = 0; i < N; i++) {        //한 점에서 증가 수열과 감소 수열의 수가 하나 겹치므로 -1을 해줌
        if (max < increase[i] + decrease[i] - 1) {
            max = increase[i] + decrease[i] - 1;    //최댓값 저장
        }
    }
 
    cout << max;
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 9663번 - N-Queen (C++)  (0) 2022.06.07
[ 백준 ] 1504번 - 특정한 최단 경로 (C++)  (0) 2022.06.06
[ 백준 ] 11779번 - 최소비용 구하기 2 (C++)  (0) 2022.06.04
[ 백준 ] 17070번 - 파이프 옮기기 1 (C++)  (0) 2022.06.03
[ 백준 ] 9251번 - LCS (C++)  (0) 2022.06.02
반응형

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

 

17070번: 파이프 옮기기 1

유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의

www.acmicpc.net

 

 

[ 문제풀이 ]

 

이 문제는 여러 가지 방법으로 풀 수 있습니다. dfs를 이용하여 모든 경우의 수를 다 구할 수도 있고, dp를 이용해서 더 빠르게 풀 수도 있습니다.

 

그중 dp를 이용한 방법에 대해서 설명드리겠습니다. 어떤 한 좌표에 파이프가 올 수 있는 경우의 수를 dp [ state ][ y ][ x ] 배열에 각각 저장하면서 마지막에 dp [ 0 ][ N ][ N ] + dp [ 1 ][ N ][ N ] + dp [ 2 ][ N ][ N ]을 출력하면 됩니다. 

 

먼저 한 점 y, x에 올 수 있는 파이프의 개수를 저장하기 위해서는 각각의 상황에 따라 다르게 구해주어야합니다.

 

예를 들어 0번 상태(가로) 일 때는 1번 상태(세로)의 파이프는 올 수 없습니다. 따라서, dp [ 0 ][ y ][ x ] = dp[ 0 ][ y ][ x - 1 ] + dp[ 2 ][ y ][ x - 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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
#include <iostream>
 
using namespace std;
 
int N;
int arr[17][17];
int dp[3][17][17];            //각 상태를 저장할 dp배열 [state][y][x] state 0:가로 1:세로 2:대각
 
int main()
{
    cin >> N;
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            cin >> arr[i][j];
        }
    }
 
    dp[0][1][2] = 1;
 
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            if (arr[i][j] != 1) {        //파이프가 움직일 수 있을 때만
                dp[0][i][j] += dp[0][i][j - 1] + dp[2][i][j - 1];    //가로, 대각
                dp[1][i][j] += dp[1][i - 1][j] + dp[2][i - 1][j];    //세로, 대각
                if (arr[i - 1][j] != 1 && arr[i][j - 1] != 1) {
                    for (int k = 0; k < 3; k++) {
                        dp[2][i][j] += dp[k][i - 1][j - 1];        //가로, 세로, 대각
                    }
                }
            }
        }
    }
 
    int ans = 0;
    for (int i = 0; i < 3; i++) {
        ans += dp[i][N][N];
    }
 
    cout << ans;
}
 
//#include <iostream>
//
//using namespace std;
//
//int N;
//int arr[16][16];
//int dp[3][16][16];
//int dx[3] = { 1,0,1 };
//int dy[3] = { 0,1,1 };
//
//void dfs(int state, int y, int x)
//{
//    if (dp[state][y][x] != -1) return;
//
//    int cur = 0;
//
//    if (state != 1 && arr[y][x + 1] == 0 && x + 1 < N) {
//        dfs(0, y, x + 1);
//        cur += dp[0][y][x + 1];
//    }
//
//    if (state != 0 && arr[y + 1][x] == 0 && y + 1 < N) {
//        dfs(1, y + 1, x);
//        cur += dp[1][y + 1][x];
//    }
//
//    bool flag = true;
//
//    for (int i = 0; i < 3; i++) {
//        int yy = y + dy[i];
//        int xx = x + dx[i];
//        if (arr[yy][xx] != 0) {
//            flag = false;
//            break;
//        }
//    }
//
//    if (flag && x + 1 < N && y + 1 < N) {
//        dfs(2, y + 1, x + 1);
//        cur += dp[2][y + 1][x + 1];
//    }
//
//    dp[state][y][x] = cur;
//}
//
//int main()
//{
//    cin >> N;
//    for (int i = 0; i < N; i++) {
//        for (int j = 0; j < N; j++) {
//            cin >> arr[i][j];
//            for (int k = 0; k < 3; k++) {
//                if (i == N - 1 && j == N - 1) {
//                    dp[k][i][j] = 1;
//                }
//                else {
//                    dp[k][i][j] = -1;
//                }
//            }
//        }
//    }
//
//    dfs(0, 0, 1);
//
//    cout << dp[0][0][1];
//}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 11054번 - 가장 긴 바이토닉 부분 수열 (C++)  (0) 2022.06.05
[ 백준 ] 11779번 - 최소비용 구하기 2 (C++)  (0) 2022.06.04
[ 백준 ] 9251번 - LCS (C++)  (0) 2022.06.02
[ 백준 ] 15686번 - 치킨 배달 (C++)  (0) 2022.06.01
[ 백준 ] 1149번 - RGB거리 (C++)  (0) 2022.05.31
반응형

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

 

9251번: LCS

LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다.

www.acmicpc.net

 

 

[ 문제풀이 ]

 

LCS란 Longest Common Subsequence 즉, 최장 공통부분 수열을 찾는 것입니다. 이 문제는 모든 수열의 부분수열 중에서 공통이 되는 가장 긴 수열의 길이를 구하는 문제입니다.

 

가장 긴 수열을 찾기 위해서는 각 수열의 요소들을 하나씩 비교해서 만약 같다면 바로 전의 최장 수열 길이의 최댓값에 +1을 해주고 같지 않다면 이전의 최장 수열 길이 중 최댓값을 대입해주면 됩니다.

 

이해하기 쉽게 다음 두 수열을 예로 들어서 설명하겠습니다.

ACAYKP
CAPCAK

먼저 문자열의 최대 길이는 1000이므로 dp[ 1001 ][ 1001 ]의 배열을 만들어줍니다. 그리고 각각의 값들을 비교하면서 위에서 설명한 대로 값들을 대입합니다. 쉬운 비교를 위해서 모든 수열의 0번째 요소를 1번으로 설정합니다.

 

 

다음으로 각 요소들을 비교해가면서 서로 같은 문자라면 dp [ i - 1 ][ j - 1 ] + 1의 값을 대입해줍니다.

 

그렇지 않다면 바로 직전까지의 수열의 최댓값 즉, dp[dp [ i - 1 ][ j ]와 dp [ i ][ j - 1 ] 중 더 큰 값을 대입해줍니다.

 

먼저 str[ 0 ][ 1 ]인 'A'와 str [ 1 ][ 1 ]인 'C'는 서로 다르기 때문에 dp [ 0 ][ 1 ]과 dp [ 1 ][ 0 ]중 더 큰 값을 dp [ 1 ][ 1 ]에 대입해줍니다.

 

다음으로 str[ 0 ][ 1 ]인 'A'와 str [ 1 ][ 2 ]인 'A'는 서로 같으므로 dp [ 0 ][ 1 ] + 1을 dp [ 1 ][ 2 ]에 대입해줍니다. 이런 식으로 쭉 대입을 해주다 보면 다음과 같은 표가 완성됩니다.

 

 

그리고 마지막에 dp[ 6 ][ 6 ]을 출력해주면 가장 긴 부분 수열의 길이를 구할 수 있습니다.

 

[ 소스 코드 ]

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
#include <iostream>
#include <string>
 
using namespace std;
 
int dp[1001][1001];
 
int main()
{
    string str[2];
 
    for (int i = 0; i < 2; i++) {
        cin >> str[i];
        str[i] = '0' + str[i];        //수열을 1부터 시작하기 위해서 맨 앞에 더미 문자를 넣음
    }
 
    for (int i = 1; i < str[0].size(); i++) {
        for (int j = 1; j < str[1].size(); j++) {    //각 문자들을 비교하며 최장 부분수열의 길이를 경신
            if (str[0][i] == str[1][j]) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
            }
            else {
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
    }
 
    cout << dp[str[0].size() - 1][str[1].size()-1];
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 11779번 - 최소비용 구하기 2 (C++)  (0) 2022.06.04
[ 백준 ] 17070번 - 파이프 옮기기 1 (C++)  (0) 2022.06.03
[ 백준 ] 15686번 - 치킨 배달 (C++)  (0) 2022.06.01
[ 백준 ] 1149번 - RGB거리 (C++)  (0) 2022.05.31
[ 백준 ] 1799번 - 비숍 (C++)  (0) 2022.05.30
반응형

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

 

1149번: RGB거리

첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나

www.acmicpc.net

 

 

[ 문제풀이 ]

 

최대 1000개의 집이 있고, 앞의 건물과 같은 색으로 칠하면 안 된다는 조건이 있습니다. 모든 조합을 뽑아 최솟값을 결정하려면 O(2^1000)이므로 터무니없는 숫자가 나옵니다. 따라서 이 문제는 dp를 활용하여 풀어주었습니다.

 

총 3N개의 배열을 3번만 탐색하면 되므로 O(N*3*3)이라는 시간복잡도가 나옵니다.

 

앞에 칠했던 건물과 같은 색을 칠하면 안되므로 먼저 dp배열의 값들을 INF로 초기화시켜줍니다. 그리고 첫 번째 집의 색깔을 정해줍니다.

 

예를 들어 첫번째 집을 빨강으로 정한다면 그 값을 제외한 모든 값들을 INF로 초기화시키고 첫 집의 빨간 집만 색칠해줍니다.

 

그렇다면 다음 집에서 빨간색으로 집을 칠하려고 할 때 초록색과 파란색 집은 INF로 초기화 되어 있기 때문에 빨간색으로 칠하는 선택지가 사라지게 됩니다. 이러한 방법으로 첫 번째 집의 색깔을 각각 한 번씩 선택해주면 답을 얻어낼 수 있습니다.

 

[ 소스 코드 ]

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
#include <iostream>
#define INF 987654321
 
using namespace std;
 
int N;
int RGB[1000][3];        //비용을 저장할 배열
int dp[1000][3];        //최솟값을 저장할 배열
 
int main()
{
    cin >> N;
    int ans = INF;
 
    for (int i = 0; i < N; i++) {
        scanf("%d %d %d", &RGB[i][0], &RGB[i][1], &RGB[i][2]);
    }
 
    for (int t = 0; t < 3; t++) {
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < 3; j++) {
                if (i == t && j == 0) {
                    dp[j][i] = RGB[0][i];    //첫 집의 색을 정함
                }
                else {
                    dp[i][j] = INF;            //나머지 집은 INF로 초기화
                }
            }
        }
 
        for (int i = 1; i < N; i++) {        //각 색깔로 칠했을 때 최솟값을 dp에 저장
            dp[i][0] = min(dp[i - 1][1] + RGB[i][0], dp[i - 1][2] + RGB[i][0]);
            dp[i][1] = min(dp[i - 1][0] + RGB[i][1], dp[i - 1][2] + RGB[i][1]);
            dp[i][2] = min(dp[i - 1][0] + RGB[i][2], dp[i - 1][1] + RGB[i][2]);
        }
 
        for (int i = 0; i < 3; i++) {        //마지막에 세 집 중 가장 비용이 적은 집 ans에 저장
            if (ans > dp[N - 1][i]) {
                ans = dp[N - 1][i];
            }
        }
    }
 
    cout << ans;
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 9251번 - LCS (C++)  (0) 2022.06.02
[ 백준 ] 15686번 - 치킨 배달 (C++)  (0) 2022.06.01
[ 백준 ] 1799번 - 비숍 (C++)  (0) 2022.05.30
[ 백준 ] 1562번 - 계단 수 (C++)  (0) 2022.05.29
[ 백준 ] 10844번 - 쉬운 계단 수 (C++)  (0) 2022.05.28
반응형

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

 

1562번: 계단 수

첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다.

www.acmicpc.net

 

 

[ 문제풀이 ]

 

https://rudalsd.tistory.com/9?category=1064612 

 

[ 백준 ] 10844번 - 쉬운 계단 수 (C++)

https://www.acmicpc.net/problem/10844 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net [ 문제풀이 ] 항상 dp문제를 풀 때는 표를 그려서 어떤 점화식을..

rudalsd.tistory.com

위의 문제와 많이 유사하지만 0~9까지의 모든 숫자가 들어가야 하므로 조금 더 까다로운 문제입니다.

 

위의 일반적인 계단 수를 구하는 문제를 풀어보시고 오는 것을 추천드립니다!!

 

쉬운 계단 수 문제와 유사하지만 한가지 개념만 더한다면 쉽게 풀 수 있는 문제입니다.

 

0~9까지의 모든 숫자가 들어가 있는 계단수는 0과 9에 모두 맞닿아있어야 합니다. 따라서 0에 맞닿아있으면 1번 비트에 저장하고, 9에 맞닿아있으면 2번 비트에 저장하고, 0과 9에 모두 닿아있으면 3번 비트에 저장합니다.

 

dp배열에 저장해 나가면 결국 3번 비트에 저장돼있는 모든 수를 더하면 정답을 구할 수 있습니다.

 

[ 소스 코드 ]

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
#include <iostream>
 
using namespace std;
 
int N;
long long dp[10][101][4];                //각 숫자가 들어갈 수 있는 개수를 저장할 배열
                                        //1 : 0과 닿음, 2 : 9와 닿음, 3 : 0, 9와 닿음
int main()
{
    cin >> N;
 
    long long cnt = 0;                    //총 개수를 저장할 변수
 
    for (int i = 1; i < 9; i++) {        //N이 1일 때 0을 제외한 각 숫자가 한번씩 들어갈 수 있으므로
        dp[i][1][0] = 1;                //모두 1로 경신
    }
 
    dp[9][1][2] = 1;
 
    for (int i = 2; i <= N; i++) {        //2자릿수 부터 돌면서
        for (int j = 0; j < 10; j++) {
            for (int k = 0; k < 4; k++) {
                if (j == 0) {            //0과 닿아있으면 k|1에 그 전의 모든 값들을 더함
                    dp[j][i][k | 1] += dp[1][i - 1][k];
                    dp[j][i][k | 1] %= 1000000000;
                }
                else if (j == 9) {        //9와 닿아있으면 k|2에 그 전의 모든 값들을 더함
                    dp[j][i][k | 2] += dp[8][i - 1][k];
                    dp[j][i][k | 2] %= 1000000000;
                }
                else {                    //아니라면 전의 값들 중 계단수들의 값들을 더함
                    dp[j][i][k] = dp[j - 1][i - 1][k] + dp[j + 1][i - 1][k];
                    dp[j][i][k] %= 1000000000;
                }
            }
        }
    }
 
    for (int i = 0; i < 10; i++) {
        cnt += dp[i][N][3];
        cnt %= 1000000000;
    }
 
    cout << cnt;
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 1149번 - RGB거리 (C++)  (0) 2022.05.31
[ 백준 ] 1799번 - 비숍 (C++)  (0) 2022.05.30
[ 백준 ] 10844번 - 쉬운 계단 수 (C++)  (0) 2022.05.28
[ 백준 ] 2407번 - 조합 (C++)  (0) 2022.05.27
[ 백준 ] 1509번 - 팰린드롬 분할 (C++)  (0) 2022.05.26
반응형

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

 

10844번: 쉬운 계단 수

첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다.

www.acmicpc.net

 

 

[ 문제풀이 ]

항상 dp문제를 풀 때는 표를 그려서 어떤 점화식을 세우면 될지 생각해보면 쉽게 답이 나오는 경우가 많았습니다.

 

이번에도 먼저 10X100 배열을 만들어서 값들을 넣어 보았고 바로 점화식이 떠올라 쉽게 답을 구할 수 있었습니다.

 

일단 첫째자리에 올 수 있는 숫자는 0을 제외한 1~9까지의 수이므로 9개입니다. 이를 표로 표현하면 다음과 같습니다.

 

 

그 후 두번째 자리에 올 수 있는 수들은 첫 번째 자리에 오는 수와 값이 1이 차이가 나면 되므로 앞의 수가 지금의 수와 절댓값이 1 차이가 나면 됩니다. 따라서 dp[ i ][ j ] = dp[ i - 1 ][ j - 1 ] + dp[ i - 1 ][ j + 1 ]이 됩니다. 하지만 0과 9는 각각 1과 8만 올 수 있으므로 예외 처리해주면 됩니다.

 

 

마지막으로 N번째 열의 값들을 모두 더해주면 N의 자리수의 계단수들을 모두 구할 수 있습니다.

 

하지만 구하고자하는 값이 int형 범위를 넘어서는 값들이고 문제의 조건에서 1,000,000,000으로 나눈 나머지 값을 출력하라고 했으므로 모든 연산이 끝나고 1,000,000,000으로 나눈 나머지 값으로 값을 경신해줍니다.

 

[ 소스 코드 ]

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
#include <iostream>
 
using namespace std;
 
int N;
long long dp[10][101];                    //각 숫자가 들어갈 수 있는 개수를 저장할 배열
 
int main()
{
    cin >> N;
 
    long long cnt = 0;                    //총 개수를 저장할 변수
 
    for (int i = 1; i < 10; i++) {        //N이 1일 때 0을 제외한 각 숫자가 한번씩 들어갈 수 있으므로
        dp[i][1] = 1;                    //모두 1로 경신
    }
 
    for (int i = 2; i <= N; i++) {        //2자릿수 부터 돌면서
        for (int j = 0; j < 10; j++) {
            if (j == 0) {                //0일 때는 1밖에 올 수 없으므로
                dp[j][i] = dp[1][i - 1];
            }
            else if (j == 9) {            //9일 때는 8밖에 올 수 없으므로
                dp[j][i] = dp[8][i - 1];
            }
            else {                        //값이 1차이나는 수들의 값을 모두 더해줌
                dp[j][i] = dp[j - 1][i - 1] + dp[j + 1][i - 1];
            }
            dp[j][i] %= 1000000000;        //더해준 값을 1000000000으로 나눈 나머지로 경신
        }
    }
 
    for (int i = 0; i < 10; i++) {
        cnt += dp[i][N];                //각 숫자마다 올 수 있는 숫자들을 더하고
        cnt %= 1000000000;                //1000000000으로 나눈 나머지로 경신해준다.
    }
 
    cout << cnt;
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 1799번 - 비숍 (C++)  (0) 2022.05.30
[ 백준 ] 1562번 - 계단 수 (C++)  (0) 2022.05.29
[ 백준 ] 2407번 - 조합 (C++)  (0) 2022.05.27
[ 백준 ] 1509번 - 팰린드롬 분할 (C++)  (0) 2022.05.26
[ 백준 ] 1208번 - 부분수열의 합 2 (C++)  (0) 2022.05.25
반응형

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

 

2407번: 조합

n과 m이 주어진다. (5 ≤ n ≤ 100, 5 ≤ m ≤ 100, m ≤ n)

www.acmicpc.net

 

 

[ 문제풀이 ]

 

먼저 nCm의 값은 n-1Cm-1 + n-1Cm으로 표현할 수 있으므로 앞에서 구한 값을 더해서 자신의 값을 계산할 수 있습니다. 따라서 위와 같은 점화식을 사용해서 dp배열을 만들어 적용시켜 주었습니다. 

 

하지만 계산해야 할 수가 정수형으로 표현할 수 있는 값을 벗어나기에 숫자들을 string의 형태로 입력받고 string을 더해주는 함수를 따로 만든 후 각 숫자들을 더해주었습니다.

 

[ 소스 코드 ]

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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
#include <iostream>
#include <string>
 
using namespace std;
 
string dp[101][101];
 
string sum(string a, string b)                //a와 b를 더해주는 함수
{
    string ans = "";
 
    int lenA = a.size();
    int lenB = b.size();
    int len = max(lenA, lenB);
    int sum = 0;
    char num;
 
    while (lenB != len) {
        b = '0' + b;
        lenB++;
    }
    while (lenA != len) {
        a = '0' + a;
        lenA++;
    }
 
    for(int i=len - 1;i>=0;i--){
        sum = a[i] + b[i] - '0' - '0' + sum;
        num = sum % 10 + '0';
        ans = num + ans;
        sum /= 10;
    }
    if (sum != 0) {
        ans = (char)(sum + '0') + ans;
    }
 
 
    return ans;
}
 
string change(int num)                        //특정 int를 string의 형태로 바꿔주는 함수
{
    string ans = "";
    if (num > 99) {
        ans = "100";
    }
    else if(num > 9) {
        ans += (char)(num / 10 + '0');
        ans += (char)(num % 10 + '0');
    }
    else {
        ans = (char)(num + '0');
    }
 
    return ans;
}
 
int main()
{
    int n, m;
    cin >> n >> m;
 
    for (int i = 1; i <= 100; i++) {
        dp[i][1] = change(i);
    }
    
 
    for (int i = 2; i <= 100; i++) {
        for (int j = 2; j <= i; j++) {
            if (i == j) {                    //n과 m이 같을 때는 1이므로
                dp[i][j] = "1";
            }
            else {                            //아닐 때는 nCm = n-1Cm-1 + n-1Cm을 대입
                dp[i][j] = sum(dp[i - 1][j - 1], dp[i - 1][j]);
            }
        }
    }
 
    cout << dp[n][m];
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 1562번 - 계단 수 (C++)  (0) 2022.05.29
[ 백준 ] 10844번 - 쉬운 계단 수 (C++)  (0) 2022.05.28
[ 백준 ] 1509번 - 팰린드롬 분할 (C++)  (0) 2022.05.26
[ 백준 ] 1208번 - 부분수열의 합 2 (C++)  (0) 2022.05.25
[ 백준 ] 17387번 - 선분 교차 2 (C++)  (0) 2022.05.24

+ Recent posts

티스토리툴바