둔필승총

www.acmicpc.net/problem/14501

문제

상담원으로 일하고 있는 백준이는 퇴사를 하려고 한다.

오늘부터 N+1일째 되는 날 퇴사를 하기 위해서, 남은 N일 동안 최대한 많은 상담을 하려고 한다.

백준이는 비서에게 최대한 많은 상담을 잡으라고 부탁을 했고, 비서는 하루에 하나씩 서로 다른 사람의 상담을 잡아놓았다.

각각의 상담은 상담을 완료하는데 걸리는 기간 Ti와 상담을 했을 때 받을 수 있는 금액 Pi로 이루어져 있다.

N = 7인 경우에 다음과 같은 상담 일정표를 보자.

1일에 잡혀있는 상담은 총 3일이 걸리며, 상담했을 때 받을 수 있는 금액은 10이다. 5일에 잡혀있는 상담은 총 2일이 걸리며, 받을 수 있는 금액은 15이다.

상담을 하는데 필요한 기간은 1일보다 클 수 있기 때문에, 모든 상담을 할 수는 없다. 예를 들어서 1일에 상담을 하게 되면, 2일, 3일에 있는 상담은 할 수 없게 된다. 2일에 있는 상담을 하게 되면, 3, 4, 5, 6일에 잡혀있는 상담은 할 수 없다.

또한, N+1일째에는 회사에 없기 때문에, 6, 7일에 있는 상담을 할 수 없다.

퇴사 전에 할 수 있는 상담의 최대 이익은 1일, 4일, 5일에 있는 상담을 하는 것이며, 이때의 이익은 10+20+15=45이다.

상담을 적절히 했을 때, 백준이가 얻을 수 있는 최대 수익을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N (1 ≤ N ≤ 15)이 주어진다.

둘째 줄부터 N개의 줄에 Ti와 Pi가 공백으로 구분되어서 주어지며, 1일부터 N일까지 순서대로 주어진다. (1 ≤ Ti ≤ 5, 1 ≤ Pi ≤ 1,000)

출력

첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다.

예제 입력 1

7 3 10 5 20 1 10 1 20 2 15 4 40 2 200

예제 출력 1

45

예제 입력 2

10 1 1 1 2 1 3 1 4 1 5 1 6 1 7 1 8 1 9 1 10

예제 출력 2

55

예제 입력 3

10 5 10 5 9 5 8 5 7 5 6 5 10 5 9 5 8 5 7 5 6

예제 출력 3

20

예제 입력 4

10 5 50 4 40 3 30 2 20 1 10 1 10 2 20 3 30 4 40 5 50

예제 출력 4

90

[문제 해설]

 N+1일째 되는 날 퇴사를 한다. 그때까지 일을 제일 많이 하면 된다. 그렇다면 다이나믹 프로그래밍을 적용했을때, 마지막에 일하는 것이 어떤 것이냐에 따라 최대값이 어떤지 비교해주면 된다.

 각 날짜에 최대를 d라는 배열에 저장해두자. 그러면 d[i]는 어떤 값이 들어올까? 이 문제의 핵심은 뒤에서부터 다이나믹 프로그래밍을 적용해야 한다는 점이다. 조건중에 n+1에는 회사에 없기때문에 일을 할 수 없다. 그래서 먼저 i날에 일을 하는 기간인 t[i]를 더한값이 n을 넘으면 안된다. 넘는다면 그 날일을 건너뛰고 그 다음날 일을 찾는 것이다. 

 만약 i+t[i]가 n을 넘지 않을 경우에는 다음과 같이 된다. 

d[i] = max(p[i] + d[i + t[i]], d[i + 1])

뒤에서부터 반복문을 쓰면 되는 것이므로 n-1에서 n이 0이 될때까지 구하면 된다. 이를 식으로 쓰면 된다.

[정답]

n = int(input())
t = []
p = []
d = [0] * (n+1)
for i in range(n):
    a, b = map(int, input().split())
    t.append(a)
    p.append(b)
# d[i]=max(p[i]+d[i+t[i]],d[i+1]) 그 일을 하는경우,하지않고 다음날 일을 하는 경우
for i in range(n - 1, -1, -1):
    if i + t[i] >n:
        d[i] = d[i + 1]
    else:
        d[i] = max(p[i] + d[i + t[i]], d[i + 1])

print(d[0])

www.acmicpc.net/problem/9625

문제

상근이는 길을 걷다가 신기한 기계를 발견했다. 기계는 매우 매우 큰 화면과 버튼 하나로 이루어져 있다.

기계를 발견했을 때, 화면에는 A만 표시되어져 있었다. 버튼을 누르니 글자가 B로 변했다. 한 번 더 누르니 BA로 바뀌고, 그 다음에는 BAB, 그리고 BABBA로 바뀌었다. 상근이는 화면의 모든 B는 BA로 바뀌고, A는 B로 바뀐다는 사실을 알게되었다.

버튼을 K번 눌렀을 때, 화면에 A와 B의 개수는 몇 개가 될까?

입력

첫째 줄에 K (1 ≤ K ≤ 45)가 주어진다.

출력

첫째 줄에 A의 개수와 B의 개수를 공백으로 구분해 출력한다.

예제 입력 1

1

예제 출력 1

0 1

[문제 해설]

문제 조건에서 A는 B로 변하고 B는 BA로 변한다는 사실에 입각해서 문제를 풀면된다. 결과적으로 A와 B의 개수를 구하면 되는 것이므로 K-1번 누르는 것과 K번 누르는 것의 차이를 구하면 된다. 

a는 k-1번의 b의 개수와 같다. b는 k-1번의 a의 개수와 b의 개수의 합과 같다. 

k = int(input())

a=[0]*46
b=[0]*46

a[0]=1

for i in range(1,k+1):
    a[i]=b[i-1]
    b[i]=a[i-1]+b[i-1]

print(a[k],b[k])

www.acmicpc.net/problem/1463

문제

정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다.

1. X가 3으로 나누어 떨어지면, 3으로 나눈다.
2. X가 2로 나누어 떨어지면, 2로 나눈다.
3. 1을 뺀다.

정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오.

입력

첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다.

출력

첫째 줄에 연산을 하는 횟수의 최솟값을 출력한다.

예제 입력 1

2

예제 출력 1

1

예제 입력 2

10

예제 출력 2

3

[문제 해설]

 1로 만들기는 다이나믹 프로그래밍의 대표적인 예이다. 1로 만드는 3가지 방법은 3으로 나누기, 2로 나누기, 1 빼기 이다. 어떤 것이 연산을 더 적게 할 수 있는지 생각하면 된다. 

 먼저 d 배열은 만든다. d 배열은 각각의 input n에서 최소의 값을 저장한 배열이다. n은 1보다 크기 때문에 반복문은 2부터 n까지 돌린다. 먼저 d[i]는 d[i-1] +1은 1빼는 것이므로 먼저 저장해두고 비교한다. 비교할 것은 3으로 나누는 것과 2로 나누는 것을 비교해주면 된다. 

3으로 나누어 떨어진다고 하면 d[i] = d[i//3] + 1 이다. 1을 더해주는 것은 3으로 나누는 연산을 해주었기 때문이다. 그럼 1을 빼는 것이 연산을 더 줄일 수 있는지 3으로 나누는 것이 더 줄일 수 있는지 구한다. 이 식이 바로

d[i]=min(d[i//3]+1, d[i])

 이다. 2로 나누는 것도 똑같이 해주면 된다.

# 1로 만들기
import sys
input = sys.stdin.readline

n = int(input())

d = [0]*1000002

for i in range(2,n+1):
    d[i] = d[i - 1] + 1
    if i%3==0:
        d[i]=min(d[i//3]+1, d[i])
    if i%2==0:
        d[i]=min(d[i//2]+1, d[i])

print(d[n])

www.acmicpc.net/problem/2579

문제

계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. <그림 1>과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점수를 얻게 된다.

예를 들어 <그림 2>와 같이 시작점에서부터 첫 번째, 두 번째, 네 번째, 여섯 번째 계단을 밟아 도착점에 도달하면 총 점수는 10 + 20 + 25 + 20 = 75점이 된다.

계단 오르는 데는 다음과 같은 규칙이 있다.

1. 계단은 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다. 즉, 한 계단을 밟으면서 이어서 다음 계단이나, 다음 다음 계단으로 오를 수 있다.
2. 연속된 세 개의 계단을 모두 밟아서는 안 된다. 단, 시작점은 계단에 포함되지 않는다.
3. 마지막 도착 계단은 반드시 밟아야 한다.

따라서 첫 번째 계단을 밟고 이어 두 번째 계단이나, 세 번째 계단으로 오를 수 있다. 하지만, 첫 번째 계단을 밟고 이어 네 번째 계단으로 올라가거나, 첫 번째, 두 번째, 세 번째 계단을 연속해서 모두 밟을 수는 없다.

각 계단에 쓰여 있는 점수가 주어질 때 이 게임에서 얻을 수 있는 총 점수의 최댓값을 구하는 프로그램을 작성하시오.

입력

입력의 첫째 줄에 계단의 개수가 주어진다.

둘째 줄부터 한 줄에 하나씩 제일 아래에 놓인 계단부터 순서대로 각 계단에 쓰여 있는 점수가 주어진다. 계단의 개수는 300이하의 자연수이고, 계단에 쓰여 있는 점수는 10,000이하의 자연수이다.

출력

첫째 줄에 계단 오르기 게임에서 얻을 수 있는 총 점수의 최댓값을 출력한다.

예제 입력 1 복사

6 10 20 15 25 10 20

예제 출력 1 복사

75

[문제 해설]

일단.acmicpc.net/problem/2579

2579번: 계단 오르기

계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. <그림 1>과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점

www.acmicpc.net

문제

계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. <그림 1>과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점수를 얻게 된다.



예를 들어 <그림 2>와 같이 시작점에서부터 첫 번째, 두 번째, 네 번째, 여섯 번째 계단을 밟아 도착점에 도달하면 총 점수는 10 + 20 + 25 + 20 = 75점이 된다.



계단 오르는 데는 다음과 같은 규칙이 있다.

계단은 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다. 즉, 한 계단을 밟으면서 이어서 다음 계단이나, 다음 다음 계단으로 오를 수 있다.

연속된 세 개의 계단을 모두 밟아서는 안 된다. 단, 시작점은 계단에 포함되지 않는다.

마지막 도착 계단은 반드시 밟아야 한다.

따라서 첫 번째 계단을 밟고 이어 두 번째 계단이나, 세 번째 계단으로 오를 수 있다. 하지만, 첫 번째 계단을 밟고 이어 네 번째 계단으로 올라가거나, 첫 번째, 두 번째, 세 번째 계단을 연속해서 모두 밟을 수는 없다.

각 계단에 쓰여 있는 점수가 주어질 때 이 게임에서 얻을 수 있는 총 점수의 최댓값을 구하는 프로그램을 작성하시오.

입력

입력의 첫째 줄에 계단의 개수가 주어진다.

둘째 줄부터 한 줄에 하나씩 제일 아래에 놓인 계단부터 순서대로 각 계단에 쓰여 있는 점수가 주어진다. 계단의 개수는 300이하의 자연수이고, 계단에 쓰여 있는 점수는 10,000이하의 자연수이다.

출력

첫째 줄에 계단 오르기 게임에서 얻을 수 있는 총 점수의 최댓값을 출력한다.

예제 입력 1 복사

6 10 20 15 25 10 20

예제 출력 1 복사

75

[문제 해설]

 일단 최대값을 구해야 된다는 사실을 알 수 있다. max()를 쓸 생각을 하고 있자.

계단을 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다. 그래서 생각할 수 있는게

r[i]의 경우에 r[i-2]에 마지막 계단을 밟는 경우와 r[i-1]의 경우에서 마지막 계단을 밟는 경우 2개 중 어느게 최대값인지 계산하면 된다고 생각했다.

 근데, 연속된 세 개의 계단을 모두 밟아서는 안된다는 조건이 있다. r[i-1]의 경우에서 마지막 계단을 밟는 경우가 연속된 세 개의 계단을 밟은것인지 아닌지 확신할 수 없다.

 그래서 r[i-3]까지 생각해야된다. 그래서 r[i]는 r[i-2]+d[i] (여기서 d[i]는 i번째 계단의 점수)와 r[i-3]+ d[i-1] + d[i] 중 최대값을 구하면 된다.

 그리고 초기값 n이 0일때는 0, n이 1일 때는 계단 첫번째 값 (d[0]), n이 2일 때는 d[0]+d[1]이 된다. 

n = int(input())
d = []
r = [0] * n
for _ in range(n):
    d.append(int(input()))

if n==0:
    print(0)
elif n==1:
    print(d[0])
elif n==2:
    print(d[0]+d[1])
else:
    r[0] = d[0]
    r[1] = d[0] + d[1]
    r[2] = max(d[0] + d[2], d[1] + d[2])

    for i in range(3, n):
        r[i] = max(r[i - 2] + d[i], r[i - 3] + d[i - 1] + d[i])

    print(r[n - 1])

www.acmicpc.net/problem/9095

문제

2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오.

아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다.

입력

첫째 줄에 n이 주어진다. (1 ≤ n ≤ 1,000)

출력

첫째 줄에 2×n 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 출력한다.

예제 입력 1 복사

2

예제 출력 1 복사

2

예제 입력 2 복사

9

예제 출력 2 복사

55

[문제 풀이]

다이나믹 프로그래밍의 대표적인 문제이다. 2 x n의 타일링은 일단 가로가 관건이다. 

타일은 1x2, 2x1 밖에 없다. n길이의 가로를 채울려면 일단 n-2길이를 채우고 1x2타일을 2개 넣으면된다.

또, n-1길이를 채우고 2x1타일을 채우면 된다.

따라서 다이나믹 프로그래밍에 따라 점화식을 세워보자.

d[i]=d[i-2]+d[i-1]

그리고 초기값을 구하면 된다. d[1]일 때는 2x1밖에 안들어간다. d[1]=1

d[2]는 2x1 타일 2개 아니면 1x2 타일 2개를 쓰면 채워진다. d[2] = 2

초기값을 채우고 나서 나머지 식을 구하면 된다.

#2Xn 타일링

n = int(input())

d = [0]*1001
d[1]=1
d[2]=2
for i in range(3,n+1):
    d[i]=d[i-2]+d[i-1]

result = d[n]%10007
print(result)

www.acmicpc.net/problem/2839

문제

상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕공장에서 만드는 설탕은 봉지에 담겨져 있다. 봉지는 3킬로그램 봉지와 5킬로그램 봉지가 있다.

상근이는 귀찮기 때문에, 최대한 적은 봉지를 들고 가려고 한다. 예를 들어, 18킬로그램 설탕을 배달해야 할 때, 3킬로그램 봉지 6개를 가져가도 되지만, 5킬로그램 3개와 3킬로그램 1개를 배달하면, 더 적은 개수의 봉지를 배달할 수 있다.

상근이가 설탕을 정확하게 N킬로그램 배달해야 할 때, 봉지 몇 개를 가져가면 되는지 그 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N이 주어진다. (3 ≤ N ≤ 5000)

출력

상근이가 배달하는 봉지의 최소 개수를 출력한다. 만약, 정확하게 N킬로그램을 만들 수 없다면 -1을 출력한다.

[풀이]

 일단 d배열의 전체를 10001로 저장해두고 d[0]=0을 해둔다. 보텀업으로 아래부터 하나하나씩 채워가기 위해서 둔것이다. 예를 들어 n을 18을 입력하였다면 18에서 5를 뺀 값은 13이다. 그럼 d[13]이 저장되어있다면 d[18]과 d[13]+1 중에서 최소값이 어떤 것인지 찾아내면 되는 것이다. 5를 뺀 d[13]이 10001이면(그러니까 5kg 3kg 두 개로 배달이 불가능한 경우일때)는 d[18]에서 3을 뺀 d[15]가 있는지 한번 살펴보는 것이다. 그럼 또 d[15]+1과 d[18]의 최소값을 찾으면 되는것이다. 예전에 '효율적인 화폐 구성' 문제에서 아이디어를 받았다. (N가지 종류의 화폐로 비용을 지불하는 문제)

n = int(input())

d = [10001]*5001
d[0]=0
for i in range(3,n+1):
    if i-5>=0 and d[i-5]!=10001:
        d[i]=min(d[i],d[i-5]+1)
    if d[i-3]!=10001:
        d[i]=min(d[i],d[i-3]+1)

if d[n]==10001:
    print(-1)
else:
    print(d[n])

www.acmicpc.net/problem/9095

문제

정수 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의 합으로 나타내는 방법의 수를 출력한다.

예제 입력 1

3 4 7 10

예제 출력 1

7 44 274

[풀이]

 먼저, 숫자가 3개 1,2,3이 있다는 사실을 안다. 4부터는 4하나로는 만들 수가 없다. 배열 d에 d[1], d[2], d[3]에 대한 값을 저장해두고 d[1], d[2], d[3]을 이용해서 나머지 4부터 10까지의 배열값을 저장할려고 했다.

4는 1에 3을 더한것, 2에 2를 더한것, 3에 1을 더한것이므로 d[4] = d[1] + d[2] + d[3] 이라고 생각할 수 있다.

5는 1에 4를 더한것, 2에 3을 더한것, 3에 2를 더한것, 4에 1을 더한것이라고 생각하면 되는데 1,2,3밖에 없으므로

d[5] = d[4] + d[3] + d[2] 까지만 하면 된다.

d[i] = d[i-1] + d[i-2] + d[i-3]이라는 점화식을 끌어오면 된다.

#1,2,3 더하기

T = int(input())
d=[0]*11
d[1]=1
d[2]=2
d[3]=4

for i in range(4,11):
    d[i]=d[i-3]+d[i-2]+d[i-1]
for i in range(T):
    n = int(input())
    print(d[n])

 컴퓨터를 이용하여 최적의 해를 구하는데 메모리 공간에는 한계가 있다. 그래서 우리는 메모리 공간을 최대한으로 활용할 수 있는 효율적인 알고리즘을 작성해야 한다.

 반대로, 다이나믹 프로그래밍은 메모리 공간을 약간 더 사용하여 연산 속도를 증가시키는 방법이다. 다이나믹 프로그래밍은 탑다운과 보텀업 두가지 방식으로 나뉘다. 그리고 메모이제이션 기법까지 알아야 된다.

 피보나치 수열은 다이나믹 프로그래밍의 대표적인 예이다. 점화식으로 표현하여 푸는 것을 다이나믹 프로그래밍의 문제라고 생각하면 된다. 

def fibo(x):
	if x==1 or x==2 :
    	return 1
    return fibo(x-1)+fibo(x-2)

다음과 같이 코드를 짜면 fibo(x)에서 x에 값이 중복되면 계속 새로 계산해야된다는 단점이 있다. 그렇다면 시간복잡도가 기하급수적으로 늘어난다. 따라서 다이나믹 프로그래밍을 통해 문제를 해결한다. 다이나믹 프로그래밍을 항상 사용할 수 수는 없고 다음 조건을 만족할 때 사용할 수 있다.

1. 큰 문제를 작은 문제로 나눌 수 있다.

2. 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다.

피보나치 수열은 다음과 같은 조건을 만족한다. 이 문제를 메모이제이션(Memoization)기법을 사용해서 해결할 수 있다.

아래는 탑다운 방식이다.

#한 번 계산된 결과를 메모이제이션하기 위한 리스트 초기화

d = [0]*100

def fibo(x):
    if x==1 or x==2:
        retun 1
    if d[x]!=0:
        return d[x]
    d[x]=fibo(x-1)+fibo(x-2)
    return d[x]

이렇게 되면 시간복잡도가 O(N)이 된다.

 이처럼 재귀함수를 이용하여 다이나믹 프로그래밍 소스코드를 작성하는 방법을, 큰 문제를 해결하기 위하여 작은 문제를 호출한다고 하여 탑다운 방식이라고 말한다. 

 반면에 단순히 반복문을 이용하여 소스코드를 작성하는 경우 작은 문제부터 차근차근 답을 도출한다고 하여 보텀업 방식이라고 한다. 피보나치 수열 문제를 보텀업으로도 풀어보자.

d = [0]*100
d[1]=1
d[2]=1
n=99

for i in range(3,n+1):
    d[i]=d[i-1]+d[i-2]  

시스템상 재귀 함수의 스택 크기가 한정되어 있을 수 있으므로 가능하다면 재귀 함수를 이용하는 탑다운 방식보다는 보텀업 방식으로 구현하는 것을 권장한다.