'동적계획법' 태그의 글 목록 (2 Page)

728x90

문제:

가로 길이가 2이고 세로의 길이가 1인 직사각형 모양의 타일이 있습니다. 이 직사각형 타일을 이용하여 세로의 길이가 3이고 가로의 길이가 n인 바닥을 가득 채우려고 합니다. 타일을 채울 때는 다음과 같이 2가지 방법이 있습니다.

*타일을 가로로 배치하는 경우

*타일을 세로로 배치하는 경우

직사각형의 가로의 길이 n이 매개변수로 주어질 때, 이 직사각형을 채우는 방법의 수를 return 하는 solution 함수를 완성해주세요.

풀이 방법:

이전 단계인 2xn 타일링과 같이 동적계획법을 사용해서 풀어야 하는 문제이다. n이 증가할 때마다 어떠한 규칙에 따라서 증가하는지 파악할 수 있다면 쉽게 문제를 풀 수 있다. n이 6~8까지 그려보면 대충 규칙을 찾아낼수 있다. 우선 n이 홀수 일 때는 타일링을 할 수 없다. 따라서 이 경우에는 항상 0이다.

그리고 타일로 만들 수 있는 모양이 한정적이라서 그 모양들을 여러 개 붙인 모양으로 반복이 된다. 규칙이 있는 타일은 다음과 같다.

이 타일들의 조합으로 반복이 되며 n=4일 때부터는 추가적인 몇개의 조합이 더 생기게 된다. 이는 이전 n(짝수만 생각했을 때)과 연관이 있기 때문에 다음과 같이 코드를 짤 수 있다.

1
2
3
4
5
6
7
8
9
def solution(n):
    dp=[0]*(n+1)
    dp[0]=1
    special=0
    for i in range(2,n+1,2):
        dp[i]=dp[i-2]*3+special*2
        special+=dp[i-2]
    answer = dp[n]%1000000007
    return answer
cs

문제 링크:

https://programmers.co.kr/learn/courses/30/lessons/12902

728x90

저작자표시 비영리 동일조건

'Algorithm > Python' 카테고리의 다른 글

[Programmers]Lv 3. 순위 (0)	2019.07.30
[Programmers]Lv3. 가장 먼 노드 (0)	2019.07.29
[BOJ]2805. 나무 자르기 (0)	2019.07.27
[BOJ]1654.랜선 자르기 (0)	2019.07.26
[BOJ]10816. 숫자 카드2 (0)	2019.07.25

728x90

문제:

지원이에게 2진 수열을 가르쳐 주기 위해, 지원이 아버지는 그에게 타일들을 선물해주셨다. 그리고 이 각각의 타일들은 0 또는 1이 쓰여 있는 낱장의 타일들이다.

어느 날 짓궃은 동주가 지원이의 공부를 방해하기 위해 0이 쓰여진 낱장의 타일들을 붙여서 한 쌍으로 이루어진 00 타일들을 만들었다. 결국 현재 1 하나만으로 이루어진 타일 또는 0 타일을 두 개 붙인 한 쌍의 00 타일들만이 남게 되었다.

그러므로 지원이는 타일로 더 이상 크기가 N인 모든 2진 수열을 만들 수 없게 되었다. 예를 들어, N=1일 때, 1만 만들 수 있고, N=2일 때는 00,11 을 만들 수 있다. (01, 10 은 만들 수 없게 되었다.) 또한 N=4일 때는 0011, 0000, 1001, 1100, 1111 등 총 5개의 2진 수열을 만들 수 있다.

우리의 목표는 N이 주어졌을 때 지원이가 만들 수 있는 모든 가짓수를 세는 것이다. 단 타일들을 무한히 많은 것으로 가정하자.

입력:

첫 번째 줄에 자연수 N이 주어진다. (N <=1,000,000)

출력:

첫 번째 줄에 지원이가 만들 수 있는 길이가 N인 모든 2진 수열의 개수를 15746으로 나눈 나머지를 출력한다.

풀이 방법:

전형적인 DP문제 이므로 점화식을 찾으면 쉽게 풀 수 있는 문제이다. 그리고 N= 5까지 숫자들을 나열해보면 규칙을 찾을 수 있다.

N=1일 때 1개, N=2일 때 2개, N=3일 때 3개, N=4일 때 5개, N=5일 때 8개 ....

즉 N=n일 때, N=n-2인 경우 + N=n-1인 경우임을 알 수 있다. 이를 바탕으로 계산을 하면서 각 계산 값에 대해 15746으로 나누면 통과할 수 있다.(맨 마지막 값에 대해서만 나누면 시간초과가 발생할 수 도 있다.)

1
2
3
4
5
6
7
8
9
10
n=int(input())
if n==1:
    print(1)
elif n==2:
    print(2)
else:
    a,b=1,2
    for i in range(3,n+1):
        a,b=(b)%15746,(a+b)%15746
    print(b%15746)
cs

728x90

저작자표시 비영리 동일조건

'Algorithm > Python' 카테고리의 다른 글

[BOJ]1712. 손익분기점 (0)	2019.07.12
[BOJ]3053. 택시 기하학 (1)	2019.07.11
[Programmers]Lv 3. 기지국 설치 (0)	2019.07.09
[Programmers]Lv 3. 섬 연결하기 (0)	2019.07.08
[Programmers]Lv 3. 단속카메라 (2)	2019.07.07

728x90

문제:

오르막 수는 수의 자리가 오름차순을 이루는 수를 말한다. 이때, 인접한 수가 같아도 오름차순으로 친다.

예를 들어, 2234와 3678,11119는 오르막 수이지만, 2232, 3676, 91111은 오르막 수가 아니다.

수의 길이 N이 주어졌을 때, 오르막 수의 개수를 구하는 프로그램을 작성하시오. 수는 0으로 시작할 수 있다.

입력:

첫째 줄에 N(1<=N<=1,000)이 주어진다.

출력:

첫째 줄에 길이가 N인 오르막 수의 개수를 10,007로 나눈 나머지를 출력한다.

풀이 방법:

2차원 동적배열을 사용해서 풀었다. 가로축을 0~9까지의 수, 세로축을 1~N까지의 길이의 수라고 설정했다. 초기에는 길이가 1인 오르막 수은 각 수 별로 1씩 있다는 것을 쉽게 알 수 있다. ( why? 0 , 1, 2, 3, 4, 5, .. , 9 = > 10개)

3까지 직접 숫자를 쓰다보면 길이가 1씩 증가할 때마다 일정한 규칙에 의해서 값이 증가한다는 것을 알 수 있다.

예를 들면 길이가 2이고 처음 0으로 시작하는 오르막 수는 동적배열에서 길이가 1인 행에서 0~9까지의 합이다.

그리고 길이가 2이고 처음 1으로 시작하는 오르막 수는 동적배열에서 길이가 1인 행에서 1~9까지의 합이다.

즉 길이가 n이고 처음 M으로 시작하는 오르막 수는 2차원 동적배열에서 길이가 n-1인 행에서 M~9까지의 합이라는 것이다. 이 규칙에 의해서 n까지 2차원 배열을 확장한 후 n번째에 있는 행의 합을 구하면 길이가 N인 오르막 수의 개수임을 알 수 있다.

1
2
3
4
5
6
7
8
n=int(input())
answer=[[1]*10]
dp=[1]*10
for i in range(1,n):
    answer.append(dp)
    for j in range(10):
        answer[i][j]=sum(answer[i-1][j:])
print(sum(answer[n-1])%10007)
cs

728x90

저작자표시 비영리 동일조건

'Algorithm > Python' 카테고리의 다른 글

[Programmers]Lv 3. 여행경로 (0)	2019.07.04
[Programmers]Lv 3. 네트워크 (2)	2019.07.03
[BOJ]1436. 영화감독 숌 (0)	2019.06.29
[BOJ]1018. 체스판 다시 칠하기 (0)	2019.06.28
[BOJ]1476. 날짜 계산 (0)	2019.06.27

728x90

문제:

n가지 종류의 동전이 있따. 각각의 동전이 나타내는 가치는 다르다. 이 동전을 적당히 사용해서, 그 가치의 합이 k원이 되도록 하고 싶다. 그 경우의 수를 구하시오. 그 경우의 수를 구하시오. 각각의 동전은 몇 개라도 사용할 수 있다.

입력:

첫째 줄에 n, k가 주어진다. (1<=n<=100, 1<=k<=10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100.000보다 작거나 같은 자연수이다.

출력:

첫째 줄에 경우의 수를 출력한다. 경우의 수는 2^31보다 작다.

풀이 방법:

대표적인 동적계획법으로 풀어야 하는 문제이다. 점화식은 다음과 같이 나타낼 수 있다.

dp[i]=dp[i-coins]

즉 예시로 보면 dp[i]=dp[i-1]+dp[i-2]+dp[i-5] 인 것이다.

하지만, 동전의 갯수는 최대 100개까지 주어질 수 있으므로 너무 많은 호출이 발생한다. (stackoverflow)

따라서 이를 해결하기 위해서 메모리제이션 방법을 사용하도록 한다.

1
2
3
4
5
6
7
8
9
10
11
12
n,k=map(int,input().split())
coins=[]
for i in range(n):
    coins.append(int(input()))
 
dp=[0]*(k+1)
dp[0]=1
 
for coin in coins:
    for i in range(coin,k+1):
        dp[i]+=dp[i-coin]
print(dp[k])
cs

728x90

저작자표시 비영리 동일조건

'Algorithm > Python' 카테고리의 다른 글

[BOJ]1476. 날짜 계산 (0)	2019.06.27
[BOJ]1002.터렛 (0)	2019.05.21
[BOJ]7568. 덩치 (0)	2019.05.19
[BOJ]2231. 분해합 (0)	2019.05.18
[BOJ]2309. 일곱 난쟁이 (0)	2019.05.17

728x90

문제:

효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규칙이 있다.

1. 포도주 잔을 선택하면 그 잔에 들어있는 포도주는 모두 마셔야 하고, 마신 후에는 원래 위치에 다시 놓아야 한다.

2. 연속으로 놓여 있는 3잔을 모두 마실 수는 없다.

효주는 될 수 있는 대로 많은 양의 포도주를 맛보기 위해서 어떤 포도주 잔을 선택해야 할지 고민하고 있다. 1부터 n까지의 번호가 붙어 있는 n개의 포도주 잔이 순서대로 테이블 위에 놓여 있고, 각 포도주 잔에 들어있는 포도주의 양이 주어졌을 때, 효주를 도와 가장 많은 양의 포도주를 마실 수 있도록 하는 프로그램을 작성하시오.

예를 들어 6개의 포도주 잔이 있고, 각각의 잔에 순서대로 6, 10, 13, 9, 8, 1만큼의 포도주가 들어 있을 때, 첫 번째, 두 번째, 네 번째, 다섯 번째 포도주 잔을 선택하면 총 포도주 양이 33으로 최대로 마실 수 있다.

입력:

첫째 줄에 포도주 잔의 개수 n이 주어진다. (1<=n<=10,000) 둘째 줄부터 n+1번째 줄까지 포도주 잔에 들어있는 포도주의 양이 순서대로 주어진다. 포도주의 양은 1,000 이하의 음이 아닌 정수이다.

출력:

첫째 줄에 최대로 마실 수 있는 포도주의 양을 출력한다.

풀이 방법:

동적계획법을 사용해서 최댓값을 찾아내야 한다. 일단 크게 두 가지 경우로 나눌 수 있다. 3이상 n 이하의 수 i에 대해서 i를 선택하는 경우와 선택하지 않는 경우이다.

i) i번째 값을 선택하고자 할 때

i번째 값을 선택하고자 하면 다시 두 개의 경우로 나눌 수 있다.

0x00 , ?0x0

전자는 i번째와 i번째를 연속해서 고르는 경우, 후자는 그렇지 않은 경우이다. 전자의 경우에는 i번째와 i번째를 더하고 거기에 dp[i-3]번째 값을 더하고, 후자의 경우에는 i번째 값에 dp[i-2]를 더하는 경우이다.

ii) i번째 값을 선택하지 않을 때

위 경우를 먼저 계산해준 후 dp[i-1] 과 dp[i] 중 최댓값을 선택하면 된다.

1
2
3
4
5
6
7
8
9
10
11
12
answer=[0]
a=int(input())
for i in range(a):
    answer.append(int(input()))
dp=[0]*(a+1)
dp[1]=answer[1]
if a>1:
    dp[2]=dp[1]+answer[2]
for i in range(3,len(dp)):
    dp[i]=max(answer[i]+answer[i-1]+dp[i-3],answer[i]+dp[i-2])
    dp[i]=max(dp[i-1],dp[i])
print(dp[a])
Colored by Color Scripter
cs

728x90

저작자표시 비영리 동일조건

'Algorithm > Python' 카테고리의 다른 글

[BOJ]1977. 완전제곱수 (0)	2019.05.03
[BOJ]1037. 약수 (0)	2019.05.02
[BOJ]2193. 이친수 (0)	2019.04.30
[BOJ]1003. 피보나치 함수 (0)	2019.04.26
[BOJ]9461.파도반 수열 (0)	2019.04.25

728x90

문제:

0과 1로만 이루어진 수를 이진수라 한다. 이러한 이진수 중 특별한 성질을 갖는 것들이 있는데, 이들을 이친수(pinary number)라 한다. 이친수는 다음의 성질을 만족한다.

1. 이친수는 0으로 시작하지 않는다.

2. 이친수에서는 1이 두 번 연속으로 나타나지 않는다. 즉, 11을 부분 문자열로 갖지 않는다.

예를 들면 1, 10, 100, 101, 1000, 1001 등이 이친수가 된다. 하지만 0010101이나 101101은 각각 1, 2번 규칙에 위배되므로 이친수가 아니다.

N(1<=N<=90)이 주어졌을 때, N자리 이친수의 개수를 구하는 프로그램을 작성하시오.

입력:

첫째 줄에 N이 주어진다.

출력:

첫째 줄에 N자리 이친수의 개수를 출력한다.

풀이 방법:

직접 1번과 2번 규칙을 만족하는 수를 찾기 위해서 N자리의 이친수를 생성하는 일을 하면 시간초과, 메모리초과가 발생하게 된다. 즉 매우 큰 수이며 많은 작업이 필요하다. 따라서 규칙이 있음을 알게 되었다.

N=1일 때에는 [ 1 ] 하나이다. N=2일 때, [10] 하나이다. N=3일 때, [100, 101] 두 개이다. N=4일 때, [1000, 1001, 1010] 세 개다. .....

이렇게 계속 반복해 나가다 보면 피보나치 함수를 이루는 것을 알 수 있다. 즉 초기 두 항이 1, 1인 피보나치 함수이다.

1
2
3
4
5
6
7
n=int(input())
a,b=1,1
count=1
while(count<n):
    a,b=b,a+b
    count+=1
print(a)
cs

728x90

저작자표시 비영리 동일조건

'Algorithm > Python' 카테고리의 다른 글

[BOJ]1037. 약수 (0)	2019.05.02
[BOJ]2156. 포도주 시식 (0)	2019.05.01
[BOJ]1003. 피보나치 함수 (0)	2019.04.26
[BOJ]9461.파도반 수열 (0)	2019.04.25
[BOJ]9095. 1,2,3 더하기 (0)	2019.04.24

728x90

문제:

다음 소스는 N번째 피보나치 수를 구하는 C++ 함수이다.

fibonacci(3) 을 호출하면 다음과 같은 일이 일어난다.

fibonacci(3) 은 fibonacci(2) 와 fibonacci(1) (첫 번째 호출)을 호출한다.

fibonacci(2) 는 fibonacci(1) (두 번째 호출)과 fibonacci(0) 을 호출한다.

두 번째 호출한 fibonacci(1) 은 1을 출력하고 1을 리턴한다.

fibonacci(0) 은 0을 출력하고, 0을 리턴한다.

fibonacci(2) 는 fibonacci(1) 과 fibonacci(0) 의 결과를 얻고, 1을 리턴한다.

첫 번째 호출한 fibonacci(1) 은 1을 출력하고, 1을 리턴한다.

fibonacci(3) 은 fibonacci(2) 와 fibonacci(1) 의 결과를 얻고, 2를 리턴한다.

1은 2번 출력되고, 0은 1번 출력된다. N이 주어졌을 때, fibonacci(N) 을 호출했을 때, 0과 1이 각각 몇 번 출력되는지 구하는 프로그램을 작성하시오.

입력:

첫째 줄에 테스트 케이스의 개수 T가 주어진다.

각 테스트 케이스는 한 줄로 이루어져 있고, N이 주어진다. N은 40보다 작거나 같은 자연수 또는 0이다.

출력:

각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다.

풀이 방법:

fibonacci(N)=fibonacci(N-1)+fibonacci(N-2)이기 때문에 0이 출력되는 횟수와 1이 출력되는 횟수도 피보나치를 이룬다. 0이 출력되는 횟수는 zero_f,zero_s라 하고, 1이 출력되는 횟수 one_f,one_s라 하고 이를 fibonnaci 함수에 넣으면 fibonacci(N)에서 0과 1이 각각 몇 번 출력되는지 알 수 있다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def new_fibo(n):
    zero_f,zero_s=1,0
    one_f,one_s=0,1
    count=1
    while(count<=n):
        zero_f,zero_s=zero_s,zero_f+zero_s
        one_f,one_s=one_s,one_f+one_s
        count+=1
    print(zero_f,one_f)
 
 
for i in range(int(input())):
    n=int(input())
    new_fibo(n)
cs

728x90

저작자표시 비영리 동일조건

'Algorithm > Python' 카테고리의 다른 글

[BOJ]2156. 포도주 시식 (0)	2019.05.01
[BOJ]2193. 이친수 (0)	2019.04.30
[BOJ]9461.파도반 수열 (0)	2019.04.25
[BOJ]9095. 1,2,3 더하기 (0)	2019.04.24
[BOJ]11052. 카드 구매하기 (0)	2019.04.23

728x90

문제:

위 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 변의 길이를 k라 했을 때, 그 변에 길이가 k인 정삼각형을 추가한다.

파도반 수열 P(N)은 나선에 있는 정삼각형의 변의 길이이다. P(1)부터 P(10)까지 첫 10개 숫자는 1,1,1,2,2,3,4,5,7,9이다.

N이 주어졌을 때, P(N)을 구하는 프로그램을 작성하시오.

입력:

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, N이 주어진다. (1<=N<=100)

출력:

각 테스트 케이스마다 P(N)을 출력한다.

풀이 방법:

수열 문제이므로 규칙을 찾는 것이 가장 중요하다. 파도반 수열은 다음과 같은 규칙을 가지고 있다.

P(N)=P(N-2)+P(N-3)

따라서 이를 처음에는 피보나치와 같이 재귀적 방법으로 풀려고 했으나 시간초과가 발생하게 되었다. 그래서 미리 길이 N의 배열을 만들어 놓고 반복문으로 배열의 인덱스를 참조하며 P(N)을 구하였다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
for i in range(int(input())):
    number=int(input())
    answer=[0]*(number+1)
    if number==1 or number==2 or number==3:
        print(1)
    elif number==4:
        print(2)
    else:
        answer[1]=1
        answer[2]=1
        answer[3]=1
        answer[4]=2
        for i in range(5,number+1):
            answer[i]=answer[i-3]+answer[i-2]
        print(answer[number])
cs

728x90

저작자표시 비영리 동일조건

'Algorithm > Python' 카테고리의 다른 글

[BOJ]2193. 이친수 (0)	2019.04.30
[BOJ]1003. 피보나치 함수 (0)	2019.04.26
[BOJ]9095. 1,2,3 더하기 (0)	2019.04.24
[BOJ]11052. 카드 구매하기 (0)	2019.04.23
[BOJ]10844. 쉬운 계단 수 (0)	2019.04.22

728x90

문제:

정수 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보다 작다.

출력:

각 테스트 케이스마다, n을 1,2,3의 합으로 나타내는 방법의 수를 출력한다.

풀이 방법:

임의의 수 N을 1,2,3의 합으로 나타내는 방법은 크게 세 가지가 있다. N-1에서 1을 더해서 N이 되는 것, N-2에서 2를 더해서 N이 되는 것, N-3에서 3을 더해서 N을 되는 경우로 해서 총 3가지이다. 따라서 이를 재귀를 이용해서 풀었다.

1
2
3
4
5
6
7
8
9
10
11
12
13
def one_two_three(n):
    if n==1:
        return 1
    elif n==2:
        return 2
    elif n==3:
        return 4
    else:
        return one_two_three(n-1)+one_two_three(n-2)+one_two_three(n-3)
 
for i in range(int(input())):
    n=int(input())
    print(one_two_three(n))
Colored by Color Scripter
cs

728x90

저작자표시 비영리 동일조건

'Algorithm > Python' 카테고리의 다른 글

[BOJ]1003. 피보나치 함수 (0)	2019.04.26
[BOJ]9461.파도반 수열 (0)	2019.04.25
[BOJ]11052. 카드 구매하기 (0)	2019.04.23
[BOJ]10844. 쉬운 계단 수 (0)	2019.04.22
[BOJ]1149. RGB거리 (0)	2019.04.21

728x90

문제:

요즘 민규네 동네에서는 스타트링크에서 만든 PS카드를 모으는 것이 유행이다.

PS카드는 PS(Problem Solving)분야에서 유명한 사람들의 아이디와 얼굴이 적혀있는 카드이다. 각각의 카드에는 등급을 나타내는 색이 칠해져 있고, 다음과 같이 8가지가 있다.

전설카드

레드카드

오렌지카드

퍼플카드

블루카드

청록카드

그린카드

그레이카드

카드는 카드팩의 형태로만 구매할 수 있고, 카드팩의 종류는 카드 1개가 포함된 카드팩, 카드 2개가 포함된 카드팩, ... 카드 N개가 포함된 카드팩과 같이 총 N가지가 존재한다.

민규는 카드의 개수가 적은 팩이더라도 가격이 비싸면 높은 등급의 카드가 많이 들어있을 것이라는 미신을 믿고 있다. 따라서, 민규는 돈을 최대한 많이 지불해서 카드 N개 구매하려고 한다. 카드가 i개 포함된 카드팩의 가격은 Pi원이다.

예를 들어, 카드팩이 총 4가지 종류가 있고, P1=1, P2=5, P3=6, P4=7인 경우에 민규가 카드 4개를 갖기 위해 지불해야 하는 금액의 최댓값은 10원이다. 2개 들어있는 카드팩을 2번 사면 된다.

마지막으로, P1=3, P2=5, P3=15, P4=16인 경우에는 3개 들어있는 카드팩과 1개 들어있는 카드팩을 구매해 18원을 지불하는 것이 최댓값이다.

카드 팩의 가격이 주어졌을 때, N개의 카드를 구매하기 위해 민규가 지불해야 하는 금액의 최댓값을 구하는 프로그램을 작성하시오. N개보다 많은 개수의 카드를 산 다음, 나머지 카드를 버려서 N개를 만드는 것은 불가능하다. 즉, 구매한 카드팩에 포함되어 있는 카드 개수의 합은 N과 같아야 한다.

입력:

첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다.(1<=N,<=1,000)

둘때 줄에는 Pi가 P1부터 Pn까지 순서대로 주어진다.(1<=Pi<=10,000)

출력:

첫째 줄에 민규가 카드 N개를 갖기 위해 지불해야 하는 금액의 최댓값을 출력한다.

풀이 방법:

동적계획법을 사용해서 문제를 풀었다. N개를 갖기 위해 지불해야 하는 금액을 구하기 위해서 N-1개까지 지불해야하는 금액을 모두 구했다. 이를 통해 N개를 갖기 위해 지불해야 하는 최댓값을 구할 수 있다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
dps=[]
number=int(input())
num_list=list(map(int,input().split()))
for i in range(number+1):
    dps.append([])
    for j in range(number+1):
        if i==j:
            dps[i].append(num_list[i-1])
        else:
            dps[i].append(0)
for i in range(2,len(dps)):
    for j in range(1,i):
        dps[i][j]=num_list[j-1]+max(dps[i-j][:i-j+1])
print(max(dps[-1]))
Colored by Color Scripter
cs

728x90

저작자표시 비영리 동일조건

'Algorithm > Python' 카테고리의 다른 글

[BOJ]9461.파도반 수열 (0)	2019.04.25
[BOJ]9095. 1,2,3 더하기 (0)	2019.04.24
[BOJ]10844. 쉬운 계단 수 (0)	2019.04.22
[BOJ]1149. RGB거리 (0)	2019.04.21
[BOJ]2163. 초콜릿 자르기 (0)	2019.04.20