반응형

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

 

9084번: 동전

우리나라 화폐단위, 특히 동전에는 1원, 5원, 10원, 50원, 100원, 500원이 있다. 이 동전들로는 정수의 금액을 만들 수 있으며 그 방법도 여러 가지가 있을 수 있다. 예를 들어, 30원을 만들기 위해서는

www.acmicpc.net

 

 

[ 문제풀이 ]

 

이 문제를 풀기 전에 다음 글을 먼저 읽고 오시는 것을 추천드립니다.

https://rudalsd.tistory.com/20

 

[ 백준 ] 12865번 - 평범한 배낭 (C++)

https://www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1

rudalsd.tistory.com

 

1. 점화식 dp[ i ][ j ] = dp[ i ][ j - coin[ i ] ] + dp[ i - 1 ][ j ] 을 통해 방법의 수를 구합니다.

 

2. dp[ N ][ M ] 을 출력합니다.

 

[ 소스코드 ]

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
#include<iostream>
 
using namespace std;
 
int T, N, M;
int arr[21];
int dp[21][10001];
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> T;
 
    while (T--) {
        cin >> N;
 
        for (int i = 1; i <= N; i++) {
            cin >> arr[i];
            dp[i][0] = 1;
            for (int j = 1; j <= M; j++) {
                dp[i][j] = 0;
            }
        }
 
        cin >> M;
 
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= M; j++) {
                if (j < arr[i]) {
                    dp[i][j] = dp[i - 1][j];
                }
                else {
                    dp[i][j] = dp[i - 1][j] + dp[i][j - arr[i]];
                }
            }
        }
 
        cout << dp[N][M] << '\n';
    }
}
cs
반응형
저작자표시 비영리 변경금지

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

[ 백준 ] 5549번 - 행성 탐사 (C++)  (0) 2023.09.15
[ 백준 ] 20160번 - 야쿠르트 아줌마 야쿠르트 주세요 (C++)  (0) 2023.09.14
[ 백준 ] 22116번 - 창영이와 퇴근 (C++)  (0) 2023.09.12
[ 백준 ] 3755번 - Double Queue (C++)  (0) 2023.09.11
[ 백준 ] 15918번 - 랭퍼든 수열쟁이야!! (C++)  (0) 2023.09.10
반응형

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

 

3067번: Coins

우리나라 화폐단위, 특히 동전에는 1원, 5원, 10원, 50원, 100원, 500원이 있다. 이 동전들로는 모든 정수의 금액을 만들 수 있으며 그 방법도 여러 가지가 있을 수 있다. 예를 들어 30원을 만들기 위해

www.acmicpc.net

 

 

[ 문제풀이 ]

 

이 문제를 풀기 전에 다음 글을 먼저 읽고 오시는 것을 추천드립니다.

https://rudalsd.tistory.com/20

 

[ 백준 ] 12865번 - 평범한 배낭 (C++)

https://www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1

rudalsd.tistory.com

 

1. 점화식 dp[ i ][ j ] = dp[ i ][ j - coin[ i ] ] + dp[ i - 1 ][ j ] 을 통해 방법의 수를 구합니다.

 

2. dp[ N ][ M ] 을 출력합니다.

 

[ 소스코드 ]

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
#include<iostream>
 
using namespace std;
 
int T;
int coin[21];
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> T;
 
    for (int t = 0; t < T; t++) {
        int N, M;
        cin >> N;
        int dp[21][10001] = { 0 };
        for (int i = 1; i <= N; i++) {
            cin >> coin[i];
            dp[i][0] = 1;
        }
 
        cin >> M;
 
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= M; j++) {
                if (j < coin[i]) dp[i][j] = dp[i - 1][j];
                else dp[i][j] = dp[i][j - coin[i]] + dp[i - 1][j];
            }
        }
 
        cout << dp[N][M] << '\n';
    }
}
cs
반응형
저작자표시 비영리 변경금지

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

[ 백준 ] 2116번 - 주사위 쌓기 (C++)  (0) 2023.08.20
[ 백준 ] 10216번 - Count Circle Groups (C++)  (0) 2023.08.19
[ 백준 ] 16965번 - 구간과 쿼리 (C++)  (0) 2023.08.17
[ 백준 ] 20007번 - 떡 돌리기 (C++)  (0) 2023.08.16
[ 백준 ] 2224번 - 명제 증명 (C++)  (0) 2023.08.15
반응형

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

 

17845번: 수강 과목

첫줄에 서윤이의 최대 공부시간 N (1 ≤ N ≤ 10,000), 과목 수 K (1 ≤ K ≤ 1,000)이 공백을 사이에 두고 주어진다.  이후 K개의 줄에 중요도 I (1 ≤ I ≤ 100,000), 필요한 공부시간 (1 ≤ T ≤ 10,000)이

www.acmicpc.net

 

 

[ 문제풀이 ]

 

이 문제를 풀기 전에 다음 글을 먼저 읽고 오시는 것을 추천드립니다.

https://rudalsd.tistory.com/20

 

[ 백준 ] 12865번 - 평범한 배낭 (C++)

https://www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1

rudalsd.tistory.com

 

[ 소스코드 ]

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
#include<iostream>
 
using namespace std;
 
int N, K;
int dp[1001][10001];
 
int main()
{
    scanf("%d %d", &N, &K);
 
    for (int i = 1; i <= K; i++) {
        int I, T;
        scanf("%d %d", &I, &T);
 
        for (int j = 1; j <= N; j++) {
            if (T > j) {
                dp[i][j] = dp[i - 1][j];
            }
            else {
                dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - T] + I);
            }
        }
    }
 
    printf("%d", dp[K][N]);
}
cs
반응형
저작자표시 비영리 변경금지

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

[ 백준 ] 17400번 - 깃발춤 (C++)  (0) 2023.04.07
[ 백준 ] 1306번 - 달려라 홍준 (C++)  (0) 2023.04.06
[ 백준 ] 1321번 - 군인 (C++)  (0) 2023.04.04
[ 백준 ] 14728번 - 벼락치기 (C++)  (0) 2023.04.03
[ 백준 ] 13424번 - 비밀 모임 (C++)  (0) 2023.04.02
반응형

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

 

14728번: 벼락치기

ChAOS(Chung-ang Algorithm Organization and Study) 회장이 되어 일이 많아진 준석이는 시험기간에도 일 때문에 공부를 하지 못하다가 시험 전 날이 되어버리고 말았다. 다행히도 친절하신 교수님께서 아래와

www.acmicpc.net

 

 

[ 문제풀이 ]

 

이 문제를 풀기 전에 다음 글을 먼저 읽고 오시는 것을 추천드립니다.

https://rudalsd.tistory.com/20

 

[ 백준 ] 12865번 - 평범한 배낭 (C++)

https://www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1

rudalsd.tistory.com

 

[ 소스코드 ]

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
#include<iostream>
 
using namespace std;
 
int N, T;
pair<int, int> arr[101];
int ans[101][10001];
 
int main()
{
    scanf("%d %d", &N, &T);
 
    for (int i = 1; i <= N; i++) {
        scanf("%d %d", &arr[i].first, &arr[i].second);
    }
 
    for (int i = 1; i <= N; i++) {
        int cost = arr[i].first;
        int point = arr[i].second;
 
        for (int j = 1; j <= T; j++) {
            if (j < cost) {
                ans[i][j] = ans[i - 1][j];
            }
            else {
                ans[i][j] = max(ans[i - 1][j], ans[i - 1][j - cost] + point);
            }
        }
    }
 
    printf("%d", ans[N][T]);
}
cs
반응형
저작자표시 비영리 변경금지

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

[ 백준 ] 17845번 - 수강 과목 (C++)  (0) 2023.04.05
[ 백준 ] 1321번 - 군인 (C++)  (0) 2023.04.04
[ 백준 ] 13424번 - 비밀 모임 (C++)  (0) 2023.04.02
[ 백준 ] 1719번 - 택배 (C++)  (0) 2023.04.01
[ 백준 ] 13023번 - ABCDE (C++)  (0) 2023.03.31
반응형

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

 

1106번: 호텔

첫째 줄에 C와 형택이가 홍보할 수 있는 도시의 개수 N이 주어진다. C는 1,000보다 작거나 같은 자연수이고, N은 20보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 각 도시에서 홍보할 때

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. 홍보 비용과 효과를 입력받고, pair<int, int> arr 배열에 저장합니다.

 

2. cus[ i ] 배열을 만들어 i명의 손님을 받았을 때 최소 비용을 저장합니다.

 

3. cus[ j + arr[ i ].second ]  = min(cus[ j + arr[ i ].second ], cus[ j ] + arr[ i ].first) 의 점화식을 통해 배열을 갱신해 줍니다.

 

4. j의 값이 C보다 크거나 같을 때 최솟값을 ans에 저장합니다.

 

5. ans를 출력합니다.

 

[ 소스코드 ]

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
#include<iostream>
 
using namespace std;
 
int C, N;
pair<int, int> arr[20];
int cus[1111];
int ans = 987654321;
 
int main()
{
    scanf("%d %d", &C, &N);
 
    fill(cus+1, cus + 1111, 987654321);
 
    for (int i = 0; i < N; i++) {
        scanf("%d %d", &arr[i].first, &arr[i].second);
    }
 
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < C; j++) {
            cus[j + arr[i].second] = min(cus[j + arr[i].second], cus[j] + arr[i].first);
 
            if (j + arr[i].second >= C) {
                ans = min(ans, cus[j + arr[i].second]);
            }
        }
    }
 
    printf("%d", ans);
}
cs
반응형
저작자표시 비영리 변경금지

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

[ 백준 ] 1414번 - 불우이웃돕기 (C++)  (0) 2023.03.13
[ 백준 ] 14950번 - 정복자 (C++)  (0) 2023.03.12
[ 백준 ] 1240번 - 노드사이의 거리 (C++)  (0) 2023.03.10
[ 백준 ] 1068번 - 트리 (C++)  (0) 2023.03.09
[ 백준 ] 27009번 - Out of Hay (C++)  (0) 2023.03.08
반응형

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

+ Recent posts

티스토리툴바