백준 알고리즘 9095 1, 2, 3 더하기 | Baekjoon Algorithm 9095: Adding 1, 2, 3

​​문제를 보자마자 0-1 knapsack 문제랑 비슷한 것 같아 DP. 문제 이겠구나 싶어서
규칙을. 찾으려고 저렇게 끄적였습니다ㅋㅋㅋ

 

처음 저 숫자들의 합만 봤을 때는 뭔가 생각이 반복이 되고 더하기가 반복이 되면서. 뭔가 했는데
전부 다 더한 값을 보니 점화식이 보이더군요

역시 DP 문제는 규칙만 찾으면 코드는 짧은 것 같습니다.

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

 

9095번: 1, 2, 3 더하기

문제 정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 7가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다. 1+1+1+1 1+1+2 1+2+1 2+1+1 2+2 1+3 3+1 정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 n이 주어진다. n은 양수이며 11보다 작다. 출력 각

www.acmicpc.net

근데 진짜로 왜 이런 규칙이 생기는지는 아무리 생각해도 모르겠더군요
​아직 DP 문제 알고리즘은 많이 안풀어봐서 그런지 어려운 것 같습니다
​
그래서 같이 스터디 하시는 분들께 여쭤봤습니다! 그러고 바로 해결!!

 

---

먼저
N이 1, 2, 3인 경우에는 기본 값으로 주어집니다.
변수 n을 표현 할 수 있는 경우의 수를 A(n)라 하면

[기본 값]

A(1) = 1
A(2) = 2
A(3) = 4

[N=4 일 때]

1 + 3을. 표현 할 수 있는 경우의 수 [=A(3)]
2 + 2를 표현 할 수 있는 경우의 수 [=A(2)]
3 + 1을 표현 할 수 있는 경우의 수 [=A(1)]

즉 A(4) = A(3) + A(2) + A(1) = 4 + 2 + 1 = 7입니다.

각각의 경우를 자세히 보면

1 + A(3)	2 + A(2)	3 + A(1)
1 + 3 1 + 1 + 2 1 + 2 + 1 1 + 1+ 1+ 1	2 + 2 2 + 1 + 1	3 + 1

마찬가지로

[N=5 일 때]

1 + 4를. 표현 할 수 있는 경우의 수 [=A(4)]
2 + 3을 표현 할 수 있는 경우의 수 [=A(3)]
3 + 2를 표현 할 수 있는 경우의 수 [=A(2)]

각각의 경우를 자세히 보면

1 + A(4)	2 + A(3)	3 + A(2)
1 + 1 + 3 1 + 1 + 1 + 2 1 + 1 + 2 + 1 1 + 1 + 1+ 1+ 1 1 + 2 + 2 1 + 2 + 1 + 1 1 + 3 + 1	2 + 3 2 + 1 + 2 2 + 2 + 1 2 + 1+ 1+ 1	3 + 2 3 + 1 + 1

이렇게 A(5)가 A(4) + A(3) + A(2) = 7+4+2 = 13 이 됩니다.

---

이전에 만든 수에서 1,2,3을 각각을 더했을 때 현재의 수가 나오므로
1을 더했을 때, 2를 더했을 때, 3을 더했을 때 현재의 수가 나오는. 각각의 이전 조합의 경우의 수를 더하면 됩니다.

만약 이 문제가 1,2,3,4 더하기 였다면
A(n)을 구하기 위해선
1 + A(n-1)
2+ A(n-2)
3 + A(n-3)
4 + A(n-4)
일 때가 A(n)이 나오는 경우의 수일 것입니다.

같은 맥락으로 이 문제가 1,2 더하기 였다면
A(n)을 구하기 위해선
1 + A(n-1)
2+ A(n-2)
일 때가 A(n)이 나오는 경우의 수겠죠?

https://github.com/mjung1798/algorithm_Java

 

mjung1798/algorithm_JAVA

JAVA algorithm study. Contribute to mjung1798/algorithm_JAVA development by creating an account on GitHub.

github.com

 

package com.jyami.baekjoon;

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main_9095 {
    public static void main(String args[]) {

        Scanner s = new Scanner(System.in);

        int num = s.nextInt();
        int max = 0;
        List<Integer> list = new ArrayList<>();


        for (int i = 0; i < num; i++) {
            int input = s.nextInt();
            list.add(input);
            if (input > max)
                max = input;
        }

        int dp[] = new int[max + 1];

        dp[1] = 1;
        dp[2] = 2;
        dp[3] = 4;

        for (int i = 4; i <= max; i++) {
            dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3];
        }

        for (Integer integer : list) {
            System.out.println(dp[integer]);
        }

    }
}

​​As soon as I saw the problem, it looked similar to the 0-1 knapsack problem, so I figured it must be a DP problem
and started scribbling like that to find the pattern lol

 

At first, when I was just looking at the sums of those numbers, it felt like something was repeating with additions going on, but I couldn't quite figure it out.
Then when I looked at the total sum of everything, the recurrence relation became clear.

As expected, with DP problems, once you find the pattern, the code ends up being pretty short.

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

 

Problem 9095: Adding 1, 2, 3

Problem: There are a total of 7 ways to represent the integer 4 as a sum of 1, 2, and 3. At least one number must be used in the sum. 1+1+1+1 1+1+2 1+2+1 2+1+1 2+2 1+3 3+1 Given an integer n, write a program to find the number of ways to represent n as a sum of 1, 2, and 3. Input: The first line contains the number of test cases T. Each test case consists of a single line with an integer n. n is a positive integer less than 11. Output:

www.acmicpc.net

But honestly, no matter how much I thought about it, I couldn't figure out why this pattern occurs.
​I guess DP problems still feel tough since I haven't solved that many yet.
​
So I asked the people in my study group! And it was solved right away!!

 

---

First,
the cases where N is 1, 2, or 3 are given as base values.
If we let A(n) be the number of ways to represent the variable n:

[Base Values]

A(1) = 1
A(2) = 2
A(3) = 4

[When N=4]

Number of ways to represent 1 + 3 [=A(3)]
Number of ways to represent 2 + 2 [=A(2)]
Number of ways to represent 3 + 1 [=A(1)]

So A(4) = A(3) + A(2) + A(1) = 4 + 2 + 1 = 7.

Looking at each case in detail:

1 + A(3)	2 + A(2)	3 + A(1)
1 + 3 1 + 1 + 2 1 + 2 + 1 1 + 1+ 1+ 1	2 + 2 2 + 1 + 1	3 + 1

Similarly,

[When N=5]

Number of ways to represent 1 + 4 [=A(4)]
Number of ways to represent 2 + 3 [=A(3)]
Number of ways to represent 3 + 2 [=A(2)]

Looking at each case in detail:

1 + A(4)	2 + A(3)	3 + A(2)
1 + 1 + 3 1 + 1 + 1 + 2 1 + 1 + 2 + 1 1 + 1 + 1+ 1+ 1 1 + 2 + 2 1 + 2 + 1 + 1 1 + 3 + 1	2 + 3 2 + 1 + 2 2 + 2 + 1 2 + 1+ 1+ 1	3 + 2 3 + 1 + 1

So A(5) becomes A(4) + A(3) + A(2) = 7+4+2 = 13.

---

Since adding 1, 2, or 3 to a previously formed number gives us the current number,
we just need to add up the number of previous combinations that result in the current number when adding 1, when adding 2, and when adding 3.

If this problem were "Adding 1, 2, 3, 4" instead,
to find A(n), we would need:
1 + A(n-1)
2+ A(n-2)
3 + A(n-3)
4 + A(n-4)
— these would be the cases that produce A(n).

By the same logic, if this problem were "Adding 1, 2",
to find A(n), we would need:
1 + A(n-1)
2+ A(n-2)
— these would be the cases that produce A(n), right?

https://github.com/mjung1798/algorithm_Java

 

mjung1798/algorithm_JAVA

JAVA algorithm study. Contribute to mjung1798/algorithm_JAVA development by creating an account on GitHub.

github.com

 

package com.jyami.baekjoon;

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main_9095 {
    public static void main(String args[]) {

        Scanner s = new Scanner(System.in);

        int num = s.nextInt();
        int max = 0;
        List<Integer> list = new ArrayList<>();


        for (int i = 0; i < num; i++) {
            int input = s.nextInt();
            list.add(input);
            if (input > max)
                max = input;
        }

        int dp[] = new int[max + 1];

        dp[1] = 1;
        dp[2] = 2;
        dp[3] = 4;

        for (int i = 4; i <= max; i++) {
            dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3];
        }

        for (Integer integer : list) {
            System.out.println(dp[integer]);
        }

    }
}