BOJ 9084 동전 about fastcampus

[rhs0266]

제가 이상적으로 생각하는 순서로 문제를 잘 해결하셨네요!

for (int i=1;i<=M;i++){
    for (int j=1;j<=N;j++){
        if (i - coin[j] >= 0) d[i] += d[i - coin[j]];
    }
}

이렇게 하시는 건 어떨까요?

[java-saeng]

선생님이 풀어주신 방법이 답이 잘 안나와서요..
혹시나 해서 제가 주석 달아놓은 내용이 맞을까요?
만약 맞다면, 주석처리 되지 않은 곳은 왜 안되고, 주석처리 된 곳은 왜 맞는건가요.. 코드 이해는 되는데, 원리 이해가 되질 않습니다..

[java-saeng]

저게 당연한건가요..?
읽으면서 1 + 1 이 2인가요를 여쭤보는 거 같기도해서요

[rhs0266]

전체 코드를 부탁드릴게용ㅎㅎㅎ

[java-saeng]

`package Dynamic_Programming;

import java.io.*;
import java.util.*;

public class Main {
    static int atoi(String str) {
        return Integer.parseInt(str);
    }
    static int N, M;
    static int coin[];
    static int dp[];
    public static void main(String[] args) throws IOException {
        input();
    }

    static void pro() {

        dp[0] = 1;

        //모든 동전을 다써서 1원 만듫고,
        //모든 동전을 다써서 2원 만듫고,
        //모든 동전을 다써서 3원 만듫고,
        //모든 동전을 다써서 M원 만듫고,

        for (int i = 1; i <= M; i++) {
            for(int j = 1; j <= N; j++){
                if(i - coin[j] >= 0) dp[i] += dp[i - coin[j]];
            }
        }

        //첫 번째 동전가지고 1원 만들고, 2원 만들고, M원 만들고
        //두 번째 동전가지고 1원 만들고, 2원 만들고, M원 만들고
        //세 번째 동전가지고 1원 만들고, 2원 만들고, M원 만들고
        //네 번째 동전가지고 1원 만들고, 2원 만들고, M원 만들고

        /*for (int i = 1; i <= N; i++) {
            for(int j = 1; j <= M; j++){
                if(j - coin[i] >= 0) dp[j] += dp[j - coin[i]];
            }
        }*/

        System.out.println(dp[M]);
    }

    static void input() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int test = atoi(br.readLine());

        while (test-- > 0) {
            N = atoi(br.readLine());

            coin = new int[N+1];
            StringTokenizer st = new StringTokenizer(br.readLine());

            for (int i = 1; i <= N; i++) {
                coin[i] = atoi(st.nextToken());
            }

            M = atoi(br.readLine());
            dp = new int[M+1];

            pro();
        }
    }
}`

입니다

[rhs0266]

1
2
1 3
4

반례입니다.

제가 말씀드린 게 틀렸네요. i, j 순서를 바꾸면 어떤 문제가 생기냐면, "동전을 사용하는 순서"가 고려되어 버려요. 즉, 4원을 만들 때, 1원 + 3원으로 만드냐, 3원 + 1원으로 만드냐를 구별하게 됩니다. 문제가 원하는 건 그것을 구별하면 안되죠.

위에 그림을 보니 순서가 다르면 값도 달라야지! 하며 푸신 것 같은데 그 부분에 있어서 문제를 아예 잘못 이해하신 것 같습니다.

[java-saeng]

처음에는 1 + 3과 3 + 1을 다르게 생각하여 파티셔닝을 했습니다. 근데 규칙성을 찾을 수 없었습니다.
옛날에 강사님에게 직접 여쭤본 문제 중에 중복을 생각하지 않고 파티셔닝을 한 기억이 있어서, 이번 문제를 풀면서 시도했는데 파티셔닝이 되었습니다. 그래서 그림을 저렇게 그린 것이었습니다!!

다만 점화식은 구했는데 for문에서 막혀서 질문을 드렸습니다.

[rhs0266]

뭐지.. 질문이 이해가 안 가요. 1+3 이랑 3+1 은 같은 게 맞습니다 이 문제는. 왜 다르게 생각해서 파티셔닝을 하셨나요?

[java-saeng]

아아... 죄송합니다.

제가 처음에는 1+3과 3+1이 같은 것으로 생각하고 파티셔닝을 했습니다. 그림에서 보시면 파란색 글씨로 쓴 부분입니다.
그러나 규칙성을 찾을 수 없었습니다.

그래서 옛날에 강사님께 직접 여쭤본 문제 중에 중복을 생각하며(1 + 3과 3 + 1은 같은 것) 경우의 수를 작성해서 규칙성을 찾지 못했지만 중복을 생각하지 않고(1+3과 3+1이 다르다고 생각하며) 모든 경우의 수를 작성한 뒤, 파티셔닝을 하여 문제를 푼 기억이 있어서 1+3과 3+1을 다르게 생각하면서 모든 경우의 수를 작성해봤습니다.
그래서 규칙성을 찾게 되어 저렇게 파티셔닝을 하게 되었습니다.

[rhs0266]

이 문제의 경우는 파티셔닝 접근 자체를 다르게 해야 합니다.

<현재>
1원 만드는 경우 다 적기, 2원 만드는 경우 다 적기, 3원 만드는 경우 다 적기, ... 을 수행한 뒤에 각각마다 공통점을 찾고 있잖아요? 하지만 이러면 해보신 대로 파티셔닝이 올바르게 수행되지 않습니다.

<수정>
첫 번째 동전을 사용해서 만드는 모든 경우 다 적기, 두 번째 동전을 사용해서 만드는 모든 경우 다 적기, 세 번째 동전을 사용해서 만드는 모든 경우 다 적기, ... 을 수행해보셔야 합니다.

그렇다면 파티셔닝이 그 자체로 이뤄지고, 대신에 dp 테이블 정의가 dp[i][j] := 1 ~ i번 동전을 써서 j 원을 만들 수 있는 경우의 수 가 되어야 자연스럽습니다. 여기까지 먼저 도달하신 다음에, 지금처럼 dp배열의 차원을 하나 낮추는 걸 고민해보시는 순서가 좋을 것 같아요.

조금 어렵지만 이번 기회에 배워가시면 dp 고수가 되실 수 있을 거에요!

[java-saeng]

선생님이 힌트를 주셔서 무조건 풀어야한다는 생각에 노력했는데 도대체 왜 저는 파티셔닝이 안되는지 모르겠습니다..

모든 경우으의 수는 이렇게 써보았습니다.

코드:

`
package Dynamic_Programming;

import java.io.*;
import java.util.*;

public class Main {
    static int atoi(String str) {
        return Integer.parseInt(str);
    }
    static int N, M;
    static int A[];
    static int dp[][];
    public static void main(String[] args) throws IOException {
        input();
    }

    static void pro() {

        for(int i = 0; i <= N; i++) dp[i][0] = 1;

        //////////////////////////////////1.
        for(int i = 1; i <= N; i++){
            for (int j = 0; j <= M; j++) {
                if(j-A[i] >= 0) dp[i][j] += dp[i][j-A[i]];
            }
        }

        ////////////////////////////////2.
        for(int j = 0; j <= M; j++){
            for(int i = 1; i <= N; i++){
                dp[i][j] += dp[i - 1][j];
            }
        }


        System.out.println(dp[N][M]);
    }

    static void input() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int test = atoi(br.readLine());

        while (test-- > 0) {
            N = atoi(br.readLine());

            A = new int[N+1];
            StringTokenizer st = new StringTokenizer(br.readLine());

            for (int i = 1; i <= N; i++) {
                A[i] = atoi(st.nextToken());
            }

            M = atoi(br.readLine());
            dp = new int[M+1][M+1];

            pro();
        }
    }
}

`

1번은 첫 번째 동전을 사용해서 모든 경우, 두 번째 동전을 사용해서 모든 경우를 구하는 것이었고,
2번은 dp[3][10]을 구할 때 1번에서 dp[3][5]를 더했고,
이제 dp[1][10]과 dp[2][10]을 더해줘야 한다는 생각으로 작성했습니다..

dp[i][j] 뜻이 1 ~ i 동전을 써서 j원을 만들 수 있는 경우의 수라고 말씀해주셨는데,
2 + 2 + 2 + 2 + 2 와 2 + 2 + 3 + 3이 다르기 때문에 2번을 작성했습니다.

[github-actions]

Stale issue message