<div id="readability-page-1" class="page"><div>                        <figure data-origin-width="0" data-origin-height="0" width="374" height="NaN" data-ke-mobilestyle="" widthcontent＂"=""><span data-url="https://blog.kakaocdn.net/dn/GvAw2/btq1s3O941O/C8YI8mRMp6LJn4HsRb1kbk/img.png" data-lightbox="lightbox" data-alt=""><img src="https://blog.kakaocdn.net/dn/GvAw2/btq1s3O941O/C8YI8mRMp6LJn4HsRb1kbk/img.png" data-origin-width="0" data-origin-height="0" width="374" height="NaN" data-ke-mobilestyle="" widthcontent＂"=""></span></figure>
<h2>문제</h2>
<p>정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 7가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다.</p>
<ul>
<li>1+1+1+1</li>
<li>1+1+2</li>
<li>1+2+1</li>
<li>2+1+1</li>
<li>2+2</li>
<li>1+3</li>
<li>3+1</li>
</ul>
<p>정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오.</p>
<h2>입력</h2>
<p>첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 n이 주어진다. n은 양수이며 11보다 작다.</p>
<pre data-ke-language="html"><code>3
4
7
10</code></pre>
<h2>출력</h2>
<p>각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다.</p>
<pre data-ke-language="html"><code>7
44
274</code></pre>
<h2>풀이</h2>
<p>이 문제는 1부터 입력한 n값까지 1, 2, 3만을 사용하여 구하는 입력한 n값을 구하는 방법의 개수를 구해야 한다.</p>
<p>처음 문제를 보고 어떻게 접근을 해야할지 몰랐지만 알고리즘 분류를 보고 dp을 사용하여 구한다는 것을 알게 되었다.</p>
<p>dp문제는 점화식을 구하고 접근을 하면 쉽게 구할 수 있기 때문에 점화식을 가장 먼저 알기 위하여 반복되는 규칙을 찾았다.</p>
<p>이 문제에 점화식을 구하게 되면 다음과 같다.</p>
<pre data-ke-language="html"><code>dp[n] = dp[n-1] + dp[n-2] + dp[n-3]</code></pre>
<p>점화식을 구한 과정은 아래 사진과 같다.</p>
<figure data-filename="스크린샷 2021-03-30 오후 6.14.22.png" data-origin-width="1070" data-origin-height="1540" width="487" height="NaN" data-ke-mobilestyle="widthContent"><span data-url="https://blog.kakaocdn.net/dn/p60hj/btq1sBekFSR/3cvKeulIIkqlk1M4bbKfAk/img.png" data-lightbox="lightbox" data-alt=""><img src="https://blog.kakaocdn.net/dn/p60hj/btq1sBekFSR/3cvKeulIIkqlk1M4bbKfAk/img.png" data-filename="스크린샷 2021-03-30 오후 6.14.22.png" data-origin-width="1070" data-origin-height="1540" width="487" height="NaN" data-ke-mobilestyle="widthContent"></span></figure>
<p>이 문제는 규칙을 찾기 굉장히 오래걸리고 까다로웠다.</p>
<p>쉽게 표현하기 위해 표로 정리 안했을 경우 한눈에 단번에 알아보기 힘들었을 것이다.</p>
<h2>코드</h2>
<pre data-ke-language="python"><code>import sys

cnt = int(sys.stdin.readline())

# n = 1 / n = 2 / n = 3일때의 갯수
dp = [1, 2, 4]
input_list = []

for _ in range(cnt):
    input_list.append(int(sys.stdin.readline()))

# 3까지의 값이 있기 때문에 3부터 시작
for i in range(3, max(input_list)):
    dp.append(dp[i-1] + dp[i-2] + dp[i-3])

for i in input_list:
    print(dp[i-1])</code></pre>                        
</div></div>

조금씩 꾸준히

문제
정수 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보다 작다.
3
4
7
10
출력
각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다.
7
44
274
풀이
이 문제는 1부터 입력한 n값까지 1, 2, 3만을 사용하여 구하는 입력한 n값을 구하는 방법의 개수를 구해야 한다.
처음 문제를 보고 어떻게 접근을 해야할지 몰랐지만 알고리즘 분류를 보고 dp을 사용하여 구한다는 것을 알게 되었다.
dp문제는 점화식을 구하고 접근을 하면 쉽게 구할 수 있기 때문에 점화식을 가장 먼저 알기 위하여 반복되는 규칙을 찾았다.
이 문제에 점화식을 구하게 되면 다음과 같다.
dp[n] = dp[n-1] + dp[n-2] + dp[n-3]
점화식을 구한 과정은 아래 사진과 같다.
이 문제는 규칙을 찾기 굉장히 오래걸리고 까다로웠다.
쉽게 표현하기 위해 표로 정리 안했을 경우 한눈에 단번에 알아보기 힘들었을 것이다.
코드
import sys
cnt = int(sys.stdin.readline())
# n = 1 / n = 2 / n = 3일때의 갯수
dp = [1, 2, 4]
input_list = []
for _ in range(cnt):
    input_list.append(int(sys.stdin.readline()))
# 3까지의 값이 있기 때문에 3부터 시작
for i in range(3, max(input_list)):
    dp.append(dp[i-1] + dp[i-2] + dp[i-3])
for i in input_list:
    print(dp[i-1])

[백준 알고리즘] 9095번 1,2,3 더하기

댓글