백준(BOJ) 9095 : 1, 2, 3 더하기 (countSum과 같은 문제)

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

 

countSum문제:   https://judge.koreatech.ac.kr/problem.php?id=1207 

 

countSum과 같은 문제로 동전1, 동전2 문제와 역시 비교해서 알아두자!

(

동전1 https://flexyduck.tistory.com/92

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

 

동전2 https://flexyduck.tistory.com/116

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

)

1,2,3 더하기 문제 =countSum 과 유사한 문제이다. 구성이 같고 순서가 다른 것을 다른 것으로 취급한다. 

for coin in coins:
    for i in range(coin, k+1):
        # coin원 동전으로 i원 만들기 -> i - coin원을 만든 후 coin원을 추가하는 것과 같음
        # 즉, coin원으로 동전을 만드는 경우의 수 -> dp[i - coin]원
        dp[i] += dp[i - coin]

어떻게 이렇게 반복문을 구성하면 요소는 같지만 순서가 다른것을 모두 같다고 취급할 수 있는건가? 
첫째행에서는 가장 기본이 되는 동전(1원)만을 이용해서 0~target까지 각각의 값을 만드는 경우의 수가 제시된다. 동전이 하나밖에 없고 그것의 가치가 가장 작은 값인 1이므로 모든 dp테이블은 1로 초기화 될것이다(경우의 수가 1가지 밖에 없음). 그후, 첫번째 행을 제외하고는 모두 기존의 것을 재사용한다. 이것이 무슨말인가? 
2원을 추가적으로 사용했을때를 생각해 보자 점화식은 dp[i]+=dp[i-coin]이다. 여기서dp[i]는 기존에 1원짜리 동전만 사용했을때의 경우의 수이고 dp[i-coin]은 해당 동전의 값어치 만큼 빼주고 1원짜리만을 사용해서 얻은 경우의수이다(즉 그후 2원짜리 동전을 살포시 얹어주어 해당목표값을 만들어 주겠다는 계산이다. 코드에는 나와있지 않지만 의미론적인 계산말이다). 이렇게 한행 한행 채우고 내려가는 과정에서 dp[i]는 새로운 동전을 사용하지 않은, 즉 이전경우의 수이고 dp[i-coin]은 새로운 동전을 사용했고 그 사용한 동전의 값만큼빼준 이전의 경우의수를 가져온다는 것이다. 가상으로는 새로운 동전을 그 위에 얹어주면 되므로! 
이와 같은 식으로 위와 같은 구성의 이중 반복문은 구성요소가 같고 순서가 다른 집합을 같은것으로 처리할 수 있는 것이다(실질적으로는 순서가 뒤죽박죽 섞이지 않게 그냥 새로운 각 원소의 집합에 마지막에 추가된다고 생각하면 편하다. 하나의 행이 진행되면서 동전의 수는 왼쪽에서 오른쪽으로 가는 동안 항상 추가될 것이고 행이 바뀔때는 새로운 동전이 추가될 것이기 때문에 중복되는 경우는 하나도 없게 된다. 

아래 그림참고.

 

--------------------------------------------------------------------------------------------------------------------------------------------

이와는 반대로 구성요소가 같아도 순서가 다르면 다른 집합을 다른것으로 처리하는 경우인 1,2,3더하기 문제의 반복문을 보면 아래와 같다. (참고로 다르다고 처리하는게 보다 일반적인 경우인것 같다. 어쨋뜬 암기는 되어야 한다. 순서만 달라도 다른것으로 처리하는 경우를 만드는 것은 내부반복문에 재료를 넣으면 된다. 반면 순서가 다른것을 같은 것으로 취급하는 것은 재료가 외부반복문에 오게 하고 그 내부구성에 대한 알맞은 수정이 필요하다)

arr=[1,2,3]

    dp[0]=1
    for i in range(n+1):
        for j in arr:
            if(i+j<=n):
                dp[i+j]+=dp[i]

 dp[i+j]+=dp[i], 이식을 단순히 최적해는 그것의 부분해로 구성된다고 볼 수 있는데 조금더 깊게 들여다볼 필요가 있다. dp[i+j]라는 기존에 얻어진 경우 +(더하기) dp[i]라는 기존의 경우에 다시 특정 수를 더하여 i+j값을 만드는 경우의 합이 dp[i+j]라고 해석할 수도 있게 된다. 

dp[i+j]라는 식은 i값을 늘리지 않고 기존에 구해져 있었던 dp[i+j] + 이전에 i라는 값으로 분명 i+j보다는 작았지만 어떤 특정한 수를 더해서 i+j가 될 수 있는 dp[i]의 합이라고 생각할수 있는 것이다 ==>> dp[i+j]=dp[i+j]+dp[i]

dp테이블과 연관성없이 위와같이만 해석하면 확장성이 없어진다.  귀찮더라도 dp[i+j]+=dp[i] 라는 식을 dp테이블과 접목시켜서 해석해 내어야 한다. 해서 위의 해석을 반복문구조와 연관지어 생각해 보겠다(이것이 dp테이블과 연관시켜 생각해 보는 것이다). 이 연관성을 생각하는데 도움을 주는 다음 두가지 질문을 보자.

의문1. 왜 i는 1씩 증가하나? 
의문2. 어떻게 위의 반복문은 구성요소가 같아도 순서가 다르면 다른 경우로 counting되는 것인가? 

"i가 1씩 증가한다"는 것의 이유와 "어떻게 위와 같은 반복문은 구성요소가 같아도 순서가 다르면 다른 경우로 counting되는 건가?" 에 관한 이유역시 모두 dp[i+j]+=dp[i]라는 식에서 그 이유를 찾을 수 있다. 위에서 설명한 바와 같이 dp[i]는 해당 내부반복문을 돌고 있을때 그때 돌고 있는 j값을 더하면 i+j가 될수 있다는 의미이다. 그리고 이렇게 값을 하나더 추가할수 있는 기회를 부여해 주는 것이 외부반복문인 for i in range(n+1)인 것이다. 물론 눈에는 보이지 않지만 외부반복문이 한번씩 돎에따라(i가 1증가함에 따라)보이지 않는 집합의 구성원소의 수는 한개씩 늘어나고 있는 것이다. (그래서 n번 돌면 아무리 못해도 최소의 값이 target이 되는 것이므로 n까지만 돌게 되는 것이다(n은 target값이고 최소값은 1이므로 1*n=n=target이므로). 이런 이유로 i는 1씩 증가하여 n번을 돌게 된다. 이때 2번째의문도 함께 풀릴수 있는데 아래그림의 별표 표시한 곳을 주목하자. dp[i+j]+=dp[i]라는 점화식을 적용하여 보면 dp[i+j]가 1,2 와 3에 해당되고 dp[i]가 1,1과 2에 해당한다. 즉dp[i]에 1을 "추가" 하면 1,1,1과 2,1이 되는데 여기서 2,1은 이미 존재하는 dp[i+j]의 1,2와 정확히 순서만 바뀐 것이다. 이렇게 구성요소가 같아도 순서가 다르면 다른 경우로 counting되게 되는 것이다!!!

 

그림참고

==>> 위와 같은 과정으로 "어떻게 위의 반복문은 구성요소가 같아도 순서가 다르면 다른 경우로 counting되는 것인가? " 에 대한 의문이 해소될 수도 있지만 너무 말이 복잡하여 이해하기 곤란한 면이 있다. 따라서 다음과 같이 이해해 높으면 위와 같은 반복문구조로 구성요소가 같고 순서가 다른것을 다른것으로 취급하는 경우를 구현해야 하는 경우 또 다시 코딩할때 더 쉽게 구현이 가능할 것이다.
  dp[i+j]+=dp[i] 에서 dp[i+j], dp[i]모두 바로 이전의 경우에서 가져오는 것이다(이전의 경우라 함은 지금이 i-1번째라면 i-2번째에서 가져온 경우라는 것이다. 다만 다른점은 dp[i+j]는 이미 i-2번째에서 구하고자 하는 값을 이미 얻은 경우의 수고 dp[i]는 i-2번째에서 가상의 j를 더했을때 이번 i-1번째에서 i+j가 나올수 있는 경우이다. 따라서 주요 반복문인 외부 반복문을 돌면서 하나의 가상요소를 추가함으로써 이번 i-1번째에는 dp[i+j]=dp[i+j]+dp[i]이다.

from sys import stdin

    
def solution(n):
    arr=[1,2,3]
    dp=[0]*(n+1)
    dp[0]=1
    for i in range(n+1):
        for j in arr:
            if(i+j<=n):
                dp[i+j]+=dp[i]
    print(dp[n])
def main():
    num=int(stdin.readline())
    for i in range(num):
        n=int(stdin.readline())
        solution(n)
        
main()

 

countSum의 테뷸레이션 풀이를 좀더 쉽게 이해할 수 있는 해법으로 설명할 수 있을까 기대했으나 동영상 풀이에서는 단순히 이 문제에서만 적용할 수 있는(구성이 같고 순서가 다른것을 다르게 취급하는 문제가 아닌) 풀이로 해결하여 실망하였다... 아래는 그 풀이다.

from sys import stdin

def solution(n):
    dp=[0]*(12)
    dp[1]=1
    dp[2]=2
    dp[3]=4
    for i in range(4, n+1):
        dp[i]=dp[i-1]+dp[i-2]+dp[i-3]
    print(dp[n])

def main():
    num=int(stdin.readline())
    for _ in range(num):
        n=int(stdin.readline())
        solution(n)

main()

 

 

-자바

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main{

    public static void solution(int target){
        int[]arr={1,2,3};
        int[]dp=new int[target+1];
        dp[0]=1;
        for(int i=0;i<target;i++){
                for (var j : arr) {
                    if(i+j<=target)dp[i+j]+=dp[i];
                }
            }
        System.out.println(dp[target]);
        }
    public static void main(String[] args) throws IOException {
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        int T=Integer.parseInt(br.readLine());
        for(int t=0;t<T;t++){
            int num=Integer.parseInt(br.readLine());
            solution(num);
        }
    }
}