ABOUT ME

-

Today
-
Yesterday
-
Total
-
  • 백준 9095 : 1, 2, 3 더하기
    알고리즘 문제/DP 2017. 10. 10. 00:18

    백준 1, 2, 3 더하기

    본문보기

    이번 문제는 경우의 수 구하는 문제이다. 해당문제는 n중 for문으로도 풀 수 있고, 재귀를 이용한 dfs 탐색(트리탐색) 으로도 풀 수 있다. 하지만 또 dp풀듯이도 풀 수 있다.

    dp 풀듯이라는 뜻은 어쨋든 굉장히 큰 길이 또는 크기를 구하는 문제이지만 서도 낮은 숫자부터 차근차근 sub-answer들을 구해내서 귀납적으로 큰 값에 대한 답 real-answer를 구하는 것이다.

    이게 바로 sub-problem , overlapping 이라는 개념인데 나는 아직 이 개념에 익숙치 않아서 이 블로그를 포스팅 하는 이유이기도 하다.


    이번문제에서 숫자는 어떻게 완성될까? 

    우선 이전 dp 문제들의 접근법을 확인해보자. 기억이 안난다면 링크참조

    <dp 입문 문제의 접근법>


    이번 문제는 어떻게 dp스럽게 풀수 있을까? (귀납적으로, 점화식처럼, 등등)

    우선 다음 경우를 확인해보자

    1 을 만드는경우 = 1   (1개)

    2 를 만드는 경우 = 1+1, 2   (2개)

    3 을 만드는 경우 = 1+1+1, 2+1, 1+2, 3   (4개)

    (1, 2, 3까지는 기본적인 원소(1,2,3)로 구성될수 있기 때문에 직접 구하였다.)


    자, 4를 만드는 경우를 생각해보자. 

    4를 만드는 경우는 다음의 경우가 가능하다. 1에서 3을 더하는방법, 2에서 2를 더하는 방법 3에서 1을 더하는 방법.

    잠깐만요, 2에서 1, 1를 더하는 방법은요? 내가 하려는 방법은 그건 3에서 1을 더하는 것과 동일한 방법으로 취급한다.

    즉 , 

    ㅇ 이미 완성된 1에서 3을 더해서 4를 완성하는 경우의 수,

    ㅇ 이미 완성된 2에서 2를 더해서 4를 완성하는 경우의 수, 

    ㅇ 이미 완성된 3에서 1을 더해서 4를 완성하는 경우의 수를 더하면 4를 완성하는 경우의 

    이전문제 느낌으로 타일링으로 한다면..

    ㅇ 이미 완성된 n-3 에서 3을 더해서 길이 n을 만드는 경우, 

    ㅇ 이미 완성된 n-2 에서 2을 더해서 길이 n을 만드는 경우,

    ㅇ 이미 완성된 n-1 에서 1을 더해서 길이 n을 만드는 경우,


    둘은 같다..... 충격!

    이렇게 문제를 해결 할 수 있다. 확실히 dfs 탐색(non memoizaiton) 이나 n중 for 문보다 훨씬 빠르므로 큰 수의 경우의 수도 도출 해낼 수 있다.











    -추가 


    조금 더 디테일하게 설명해본다. 이때 d[n]은 어떤 경우의수를 담는가? 

    ... n을 완성하는 경우의수!


    아니아니,, 그보다 더 정확하게는 n을 완성하는 경우의 중복을 허용하는 수야  

    자, 연습해볼게요 "n을 완성하는 경우의 중복을 허용하는 수"

    "n을 완.... 완성하는 경우의수.!"


    <ㅠ.ㅠ ㅋ....그래 심적으로 와닿지 않으면 따라하기도 힘들지...(짤방은 이 의미로 그려진것같지않지만)>



    어쨌든 n을 완성하기 위해 어떤 경우의수를 참조했는가 생각해보자.

    우리는 n을 완성하는데 기본적으로 다음과 같은 순서를 따랐다.


    n을 완성하는데는... (즉 dp 배열을 완성해나가는 데는)

    n-a[0]에서 a[0] 을 더해서 완성하는 경우의 수 

    n-a[1]에서 a[1] 을 더해서 완성하는 경우의 수

    n-a[2]에서 a[2] 을 더해서 완성하는 경우의 수.

    ... 

    n-a[k]에서 a[k]을 더해서 완성하는 경우의 수. 를 모두 더한다. 


    맨 마지막항을 어떤것으로 결정하는 가와 같다. (그림참고)


    자, 임의의 수 m을 완성하는데 다음의 경우의 수가 있다고 하자  

    a[1]+a[0]+a[1]

    a[1]+a[1]+a[0]  ...

    ㅇㅣ 둘은 중복된다. 즉, 순열과 같다. 더해지는 순서에 "상관있게" 경우의 수를 고유하게 매긴다. 

    좀더 이해를 돕기위해 숫자로 보자 4를 완성하는데 다음의 경우의 수가 있다고 하자.

    1+2+1

    1+1+2  ....  더해지는 순서를 상관있게 경우의수를 고려하기 때문에 이 녀석들 또한 고유한 경우의 수로 본다.


    왜 이렇게 되는걸까?

    바로 위에 서술했던 n을 완성해나가는 방법과 상관이 있다.

    1을 완성하는 경우의 수는? 1,    

    2를 완성하는 경우의 수는? 1+1; 2.

    3을 완성하는 경우의 수는? 2+1; 1+2  (일부만 보자)

    4를 완성하는 경우의 수는? 1+2+1; 2+1+1 , 1+1+2


    위의 경우, 4를완성하는데 논리를봐보자 (일부만)

    (4-1)을 완성하는 경우의수 + (4-2)을 완성하는 경우의수


    풀어서보면

    3을 완성하는 경우의수 (1+2 포함, 여기서 1만 더하면 4가됨)

    +

    2을 완성하는 경우의수 (1+1 포함, 여기서 2만 더하면 4가됨)

    이렇게되면 4를 완성하는 경우에 1+2+1, 1+1+2가 모두 고유한 것처럼 다루는 논리가 되는 것이다.


    애초에 3을 완성하는 경우의 수도 중복된다.

    1+2와 2+1을 1개의 1과 1개의 2로 완성되는 것이다.


    만약 우리가 중복되지 않은 경우의 수만 원한다 할 때.

    즉, 조합의 경우를 원한다 할땐 어떡해야할까? 마치 다음처럼...


    4를 완성하는데는 경우의 수 5개가 있다.

    4개의 1로 완성하는 경우

    2개의 1과 1개의 2로 완성되는 경우,

    2개의 2로 완성되는 경우

    1개의 1과 1개의 3으로 완성되는 경우

    1개의 4로 완성되는 경우


    이렇게 하려면

    n을 완성하는 방법을 바꿔야한다. 

    dp 배열 d[i]을 맨 마지막 항(d[i-1])을 비워두고  그 항에 들어갈 수 있는 수 a[j]를 채워넣는 것에서

    즉, d[i]+=d[i-a[j]] , where i= 1~n, j= 1~k    ( for i -> n; for j -> k ) 에서


    매 배열 d[j], where j= 1~n은 a[i]로 완성될 수 있는가를 체크하고, 체크된다면 d[j-a[i]]만큼더한다.

    d[j]+=d[j-a[i]], where j= 1~n, i= 1~k    (for i->k; for j->n) 으로 바꿔야한다.

    왜냐하면 d[j]는 정확히 i-1까지의 수를 이용해 생성한 d[h] 경우의 수를 참고하기때문이다.
    여기서h<j<n


    이 문제는 다음문제 백준문제 동전으로 살펴본다.


    다음 경우의 수 문제 보기

    백준 동전문제



    '알고리즘 문제 > DP' 카테고리의 다른 글

    백준1126 같은탑  (0) 2017.12.05
    BOJ 1520 : 내리막길  (0) 2017.11.11
    백준 9095 : 1, 2, 3 더하기  (0) 2017.10.10
    백준 11727: 2*n 타일링2  (0) 2017.10.09
    백준 11726 : 2*n 타일링  (1) 2017.10.09
    백준 1463 : 1로 만들기  (2) 2017.10.09

    댓글 0

Designed by Tistory.