졍's 기술 블로그

카드 구매하기 2

티어 : Silver 1
시간 제한 : 1 초
메모리 제한 : 256 MB
알고리즘 분류 : 다이나믹 프로그래밍

문제

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

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

• 전설카드
• 레드카드
• 오렌지카드
• 퍼플카드
• 블루카드
• 청록카드
• 그린카드
• 그레이카드

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

민규는 지난주에 너무 많은 돈을 써 버렸다. 그래서 오늘은 돈을 최소로 지불해서 카드 N개를 구매하려고 한다. 카드가 i개 포함된 카드팩의 가격은 Pi원이다.

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

P1 = 5, P2 = 2, P3 = 8, P4 = 10인 경우에는 카드가 2개 들어있는 카드팩을 2번 사면 4원이고, 이 경우가 민규가 지불해야 하는 금액의 최솟값이다.

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

입력

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

둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1 ≤ Pi ≤ 10,000)

출력

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

예제 입출력

Algorithm

Dynamic Programming
4장의 카드를 구매할 때 (1, 3), (2, 2) 고려
☞ (1, 3) : 1장의 카드를 구매하는 데 최적의 답 + 3장의 카드를 구매하는 데 최적의 답
☞ (2, 2) : 2장의 카드를 구매하는 데 최적의 답 + 2장의 카드를 구매하는 데 최적의 답

Code

N = int(input())
cards = list(map(int, input().split()))

dp = [10000*N] * (N+1)
dp[1] = cards[0]

for i in range(2, N+1):
    for j in range(1, N+1):
        # 현재 dp table에 담겨있는 값
        # j장 카드 구매하는 데 최적의 값 + i-j장 카드 구매하는 데 최적의 값
        # 카드팩으로 딱 맞게 구매할 때의 값 중 최솟값으로 갱신
        dp[i] = min(dp[i], dp[j]+dp[i-j], cards[i-1])
print(dp[-1])

메모리: 30840 KB
시간: 536 ms

카드 구매하기

티어 : Silver 1
시간 제한 : 1 초
메모리 제한 : 256 MB
알고리즘 분류 : 다이나믹 프로그래밍

문제

요즘 민규네 동네에서는 스타트링크에서 만든 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 = 5, P2 = 2, P3 = 8, P4 = 10인 경우에는 카드가 1개 들어있는 카드팩을 4번 사면 20원이고, 이 경우가 민규가 지불해야 하는 금액의 최댓값이다.

마지막으로, 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개를 갖기 위해 지불해야 하는 금액의 최댓값을 출력한다.

예제 입출력

Algorithm

Dynamic Programming
4장의 카드를 구매할 때 (1, 3), (2, 2) 고려
☞ (1, 3) : 1장의 카드를 구매하는 데 최적의 답 + 3장의 카드를 구매하는 데 최적의 답
☞ (2, 2) : 2장의 카드를 구매하는 데 최적의 답 + 2장의 카드를 구매하는 데 최적의 답

Code

N = int(input())
cards = list(map(int, input().split()))

dp = [0] * (N+1)
dp[1] = cards[0]

for i in range(2, N+1):
    for j in range(1, N+1):
        # j장의 카드를 구매하는 데 최적의 답 + i-j장의 카드를 구매하는 데 최적의 답
        # card팩으로 현재 구매 개수(i)를 한 번에 사는 경우의 답
        # 현재 dp table에 담겨있는 답 중 최댓값으로 갱신
        dp[i] = max(dp[j] + dp[i-j], cards[i-1], dp[i])

print(dp[-1])

메모리: 30840 KB
시간: 508 ms

2xn 타일링 2

티어 : Silver 3
시간 제한 : 1 초
메모리 제한 : 256 MB
알고리즘 분류 : 다이나믹 프로그래밍

문제

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

아래 그림은 2×17 직사각형을 채운 한가지 예이다.

입력

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

출력

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

예제 입출력

Algorithm

Dynamic Programming
점화식 : dp[n] = 2 * dp[n-1] + 1 (n = 짝수)
           dp[n] = 2 * dp[n-1] - 1 (n = 홀수)

Code

n = int(input())
dp = [0] * (n+1)
dp[1] = 1

for num in range(2, n+1):
    # num이 짝수일 때
    if num % 2 == 0:
        dp[num] = 2 * dp[num-1] + 1
    else: # 홀수일 때
        dp[num] = 2 * dp[num-1] - 1
print(dp[n]%10007)

메모리: 30840 KB
시간: 72 ms

2xn 타일링

티어 : Silver 3
시간 제한 : 1 초
메모리 제한 : 256 MB
알고리즘 분류 : 다이나믹 프로그래밍

문제

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

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

입력

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

출력

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

예제 입출력

Algorithm

Dynamic Programming
점화식 : dp[n] = dp[n-2] + dp[n-1]

Code

n = int(input())
dp = [0] * (n+1)
dp[1] = 1
if n > 1:
    dp[2] = 2

for num in range(3, n+1):
    dp[num] = dp[num-1] + dp[num-2]
print(dp[n]%10007)

메모리: 30840 KB
시간: 68 ms

지름길

티어 : Silver 1
시간 제한 : 2 초
메모리 제한 : 128 MB
알고리즘 분류 : 다이나믹 프로그래밍, 그래프 이론, 다익스트라

문제

매일 아침, 세준이는 학교에 가기 위해서 차를 타고 D킬로미터 길이의 고속도로를 지난다. 이 고속도로는 심각하게 커브가 많아서 정말 운전하기도 힘들다. 어느 날, 세준이는 이 고속도로에 지름길이 존재한다는 것을 알게 되었다. 모든 지름길은 일방통행이고, 고속도로를 역주행할 수는 없다.

세준이가 운전해야 하는 거리의 최솟값을 출력하시오.

입력

첫째 줄에 지름길의 개수 N과 고속도로의 길이 D가 주어진다. N은 12 이하인 양의 정수이고, D는 10,000보다 작거나 같은 자연수이다. 다음 N개의 줄에 지름길의 시작 위치, 도착 위치, 지름길의 길이가 주어진다. 모든 위치와 길이는 10,000보다 작거나 같은 음이 아닌 정수이다. 지름길의 시작 위치는 도착 위치보다 작다.

출력

세준이가 운전해야하는 거리의 최솟값을 출력하시오.

예제 입출력

Algorithm

dijkstra 알고리즘 - 힙
1. 지름길을 입력 받아 graph 생성
    ➝ 도착 지점이 고속도로의 길이보다 큰 경우 graph에 추가하지 않음
2. 지름길이 아닌 길도 graph에 추가
    ➝ 중간에 끊겨있는 길도 같이 추가
3. D 위치의 최단 거리 출력

Code

import sys
import heapq

INF = int(1e9)
input = sys.stdin.readline

def dijkstra(start):
    queue = []
    
    # 첫 번째 칸으로 가는 최단 경로 0으로 설정
    heapq.heappush(queue, (start, 0))
    distance[start] = 0
    
    while queue:
        
        # 큐에서 꺼내기
        dist, now = heapq.heappop(queue)
        
        # 방문한 노드라면 무시
        if distance[now] < dist:
            continue
        
        # 인접 노드 확인
        for next in graph[now]:
            cost = dist + next[1]
            
            # cost가 인접노드까지 가는 데 최소 거리라면 갱신하고 큐에 추가
            if cost < distance[next[0]]:
                distance[next[0]] = cost
                heapq.heappush(queue, (cost, next[0]))
    

N, D = map(int, input().split())
graph = [[] for _ in range(D+1)]
distance = [INF] * (D+1)
for _ in range(N):
    start, end, length = map(int, input().split())
    # 도착 지점이 고속도로의 길이보다 큰 경우 graph에 추가하지 않음
    if end > D:
        continue
    graph[start].append((end, length))

    # 지름길이 아닌 길도 graph에 추가
    if (end, end - start) not in graph[start]:
        graph[start].append((end, end - start))
        
for i in range(D):
    # graph의 현재 INDEX에 다음 칸 까지의 거리 추가
    graph[i].append((i+1, 1))

dijkstra(0)
print(distance[-1])

메모리: 32928 KB
시간: 72 ms

가장 긴 감소하는 부분 수열

티어 : Silver 2
시간 제한 : 1 초
메모리 제한 : 256 MB
알고리즘 분류 : 다이나믹 프로그래밍

문제

수열 A가 주어졌을 때, 가장 긴 감소하는 부분 수열을 구하는 프로그램을 작성하시오.

예를 들어, 수열 A = {10, 30, 10, 20, 20, 10} 인 경우에 가장 긴 감소하는 부분 수열은 A = {10, 30, 10, 20, 20, 10}  이고, 길이는 3이다.

입력

첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000)이 주어진다.

둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000)

출력

첫째 줄에 수열 A의 가장 긴 감소하는 부분 수열의 길이를 출력한다.

예제 입출력

Algorithm

가장 긴 감소하는 부분 수열은 가장 긴 증가하는 부분 수열을 이용
dp[i] : i번째 원소를 마지막으로 하는 부분 증가수열의 길이
1. 입력 받는 수열을 reverse
2. 가장 긴 증가하는 부분 수열 찾기

Code

N = int(input())
A = list(map(int, input().split()))

# 수열 reverse
A.reverse()

dp = [1] * N

for i in range(1, N):
  for j in range(i):
    if A[j] < A[i]:
      dp[i] = max(dp[i], dp[j] + 1)

print(max(dp))

메모리: 30864 KB
시간: 196 ms

가장 긴 증가하는 부분 수열

티어 : Silver 2
시간 제한 : 1 초
메모리 제한 : 256 MB
알고리즘 분류 : 다이나믹 프로그래밍

문제

수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.

예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다.

입력

첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000)이 주어진다.

둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000)

출력

첫째 줄에 수열 A의 가장 긴 증가하는 부분 수열의 길이를 출력한다.

예제 입출력

Algorithm

dp[i] : i 번째 원소를 마지막으로 하는 부분 증가 수열의 최대 길이
1. 리스트를 이중 for문으로 돌면서 자신보다 작은 index에 값이 작은 수가 몇 개 있는지 확인
    ➝ i : 1 ~ N-1, j : 0 ~ i
2. j번째 원소가 i번째 원소보다 작으면 i번째 dp Table의 값과 j번째 dp Table의 값 + 1 중 큰 값으로 dp Table 갱신

Code

N = int(input())
A = list(map(int, input().split()))

dp = [1] * N

for i in range(1, N):
  for j in range(i):
    if A[j] < A[i]:
      dp[i] = max(dp[i], dp[j] + 1)

print(max(dp))

메모리: 30860 KB
시간: 200 ms

1, 2, 3 더하기

티어 : Silver 3
시간 제한 : 1 초 (추가 시간 없음)
메모리 제한 : 512 MB
알고리즘 분류 : 다이나믹 프로그래밍

문제

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

예제 입출력

Algorithm

dp[i] : 1, 2, 3의 합으로 i를 만들 수 있는 개수
dp[i] = dp[i-3] + dp[i-2] + dp[i-1]

Code

T = int(input())
for _ in range(T):
  n = int(input())

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

  print(dp[n])

메모리: 30860 KB
시간: 72 ms