A. 문제 정수 X가 주어진다.정수 X에 다음 4가지 연산을 사용할 수 있다. X가 5로 나누어떨어지면, 5로 나눈다X가 3로 나누어떨어지면, 3으로 나눈다X가 2로 나누어떨어지면, 2로 나눈다X에서 1을 뺀다 정수 X가 주어졌을 때, 연산 4개를 적절히 사용하여 1을 만든다. 이때 연산을 사용하는 횟수의 최솟값을 구하라. a. 예를 들면. 정수 26이면, 산을 사용하는 횟수의 최솟값이 3이다. 26 - 1 = 25 (4)25 / 5 = 5 (1)5 / 5 = 1 (1) b. 입력 조건 첫째 줄에 정수 X가 주어진다.1 <= X <= 30,000 c. 출력 조건 첫째 줄에 연산을 하는 횟수의 최솟값을 출력한다.
# 정수 X를 입력 받기
x = int(input())
# 앞서 계산된 결과를 저장하기 위한 DP 테이블 초기화
d = [0] * 1000001
# 다이나믹 프로그래밍(Dynamic Programming) 진행(보텀업)
for i in range(2, x + 1):
# 현재의 수에서 1을 빼는 경우
d[i] = d[i - 1] + 1
# 현재의 수가 2로 나누어 떨어지는 경우
if i % 2 == 0:
d[i] = min(d[i], d[i // 2] + 1)
# 현재의 수가 3으로 나누어 떨어지는 경우
if i % 3 == 0:
d[i] = min(d[i], d[i // 3] + 1)
# 현재의 수가 5로 나누어 떨어지는 경우
if i % 5 == 0:
d[i] = min(d[i], d[i // 5] + 1)
print(d[x])
개미전사
A. 문제 개미 전사는 메뚜기 마을의 식량창고를 몰래 공격한다.메뚜기 마을의 식량창고는 일직선으로 되어 있다.각 식량창고에는 정해진 수의 식량을 저장하고 있으며 개미 전사는 식량창고를 선택적으로 약탈하여 식량을 빼앗을 예정이다.메뚜기 정찰병은 일직선상에 존재하는 식량창고 중에서 서로 인접한 식량창고가 공격받으면 알아챌 수 있다. 따라서 개미 전사가 정찰병에게 들키지 않고 식량창고를 약탈하기 위해서는 최소한 한 칸 이상 떨어진 식량창고를 약탈해야 한다. 개미 전사는 식량창고 N에 대한 정보가 주어졌을 때 얻을 수 있는 식량의 최댓값을 구하는 프로그램을 작성하라. a. 예를 들면. 식량창고 4개가 아래와 같이 존재한다고 가정한다. [1, 3, 1, 5] 이때 개미 전사는 두 번째 식량창고와 네 번째 식량 창고를 선택했을 때 최댓값인 8개의 식량을 빼앗을 수 있다. b. 입력 조건 첫째 줄에 식량창고의 개수 N이 주어진다3 <= N <= 100둘째 줄에 공백으로 구분되어 각 식량창고에 저장된 식량의 개수 K가 주어진다0 <= K <= 1000 c. 출력 조건 첫째 줄에 개미 전사가 얻을 수 있는 식량의 최댓값을 출력하라.
# 정수 N을 입력 받기
n = int(input())
# 모든 식량 정보 입력 받기
array = list(map(int, input().split()))
# 앞서 계산된 결과를 저장하기 위한 DP 테이블 초기화
d = [0] * 100
# 다이나믹 프로그래밍(Dynamic Programming) 진행 (보텀업)
d[0] = array[0]
d[1] = max(array[0], array[1])
for i in range(2, n):
d[i] = max(d[i - 1], d[i - 2] + array[i])
# 계산된 결과 출력
print(d[n - 1])
바닥 공사
A. 문제 가로 길이가 N, 세로 길이가 2인 직사각형 형태의 얇은 바닥이 있다.이 바닥을 1x2, 2x1, 2x2 덮개를 이용해 채우고자 한다. 이때 바닥을 채우는 모든 경우의 수를 구하는 프로그램을 작성하라. a. 예를 들면. 2x3 크기의 바닥을 채우는 경우의 수는 5가지이다. b. 입력 조건 첫째 줄에 N이 주어진다.1 <= N <= 1,000 c. 출력 조건 첫째 줄에 2xN 크기의 바닥을 채우는 방법의 수를 796,796으로 나눈 나머지를 출력한다.
# 정수 N을 입력 받기
n = int(input())
# 앞서 계산된 결과를 저장하기 위한 DP 테이블 초기화
d = [0] * 1001
# 다이나믹 프로그래밍(Dynamic Programming) 진행 (보텀업)
d[1] = 1
d[2] = 3
for i in range(3, n + 1):
d[i] = (d[i - 1] + 2 * d[i - 2]) % 796796
# 계산된 결과 출력
print(d[n])
효율적인 화페 구성
A. 문제 N가지 종류의 화폐가 있다. 화폐들의 개수를 최소한으로 이용해서 가치의 합이 M원이 되도록 만들어라. 각 화폐는 몇 개라도 사용할 수 있다. a. 예를 들면. 2원, 3원 단위의 화폐가 있을 때 15원을 만들기 위해서는 3원을 5개 사용하는 것이 가장 최소한의 화폐 개수다. b. 입력 조건 첫째 줄에 N, M이 주어진다1 <= N <= 1001 <= M <= 10,000이후 N개 줄에 각 화폐의 가치가 주어진다.화폐의 가치는 10,000보다 작거나 같은 자연수 c. 출력 조건 첫째 줄에 경우의 수 X를 출력한다.불가능할 때는 -1을 출력한다.
# 정수 N, M을 입력 받기
n, m = map(int, input().split())
# N개의 화폐 단위 정보를 입력 받기
array = []
for i in range(n):
array.append(int(input()))
# 한 번 계산된 결과를 저장하기 위한 DP 테이블 초기화
d = [10001] * (m + 1)
# 다이나믹 프로그래밍(Dynamic Programming) 진행(보텀업)
d[0] = 0
for i in range(n):
for j in range(array[i], m + 1):
if d[j - array[i]] != 10001: # (i - k)원을 만드는 방법이 존재하는 경우
d[j] = min(d[j], d[j - array[i]] + 1)
# 계산된 결과 출력
if d[m] == 10001: # 최종적으로 M원을 만드는 방법이 없는 경우
print(-1)
else:
print(d[m])
금광
A. 문제 n * m 크기의 금광이 있다. 금광은 1* 1 크기의 칸으로 나누어져 있으며, 각 칸은 특정한 크기의 금이 들어 있다. 채굴자는 첫 번째 열부터 출발하여 금을 캐기 시작한다. 맨 처음에는 첫번째 열의 어느 행에서든 출발할 수 있다. 이후에 m번에 걸쳐서 매번 오른쪽 위, 오른쪽, 오른쪽 아래 3가지 중 하나의 위치로 이동해야 한다. 결과적으로 채굴자가 얻을 수 있는 금의 최대 크기를 출력하는 프로그램을 작성하라. a. 예를 들면. 3 * 4 크기의 금광이 존재한다고 가정하자.
가장 왼쪽 위의 위치를 (1, 1), 가장 오른쪽 아래의 위치를 (n, m)이라고 할 때, 위 예시에서는 (2, 1) -> (3, 2) -> (3, 3) -> (3, 4)의 위치로 이동하면 총 19만큼의 금을 채굴할 수 있으며, 이때의 값이 최댓값이다. b. 입력 조건 첫째 줄에 테스트 케이스 T가 입력된다 1 <= T <= 1000 매 테스트 케이스 첫째 줄에 n과 m이 공백으로 구분되어 입력된다. (1 <= n, m <= 20) 둘째줄에 n * m개의 위치에 매장된 금의 개수와 공백으로 구분되어 입력된다. (1 <= 각 위치에 매장된 금의 개수 <= 100) c. 출력 조건 테스트 케이스마다 채굴자가 얻을 수 있는 금의 최대 크기를 출력한다.각 테스트 케이스는 줄 바꿈을 이용해 구분한다.
# 테스트 케이스(Test Case) 입력
for tc in range(int(input())):
# 금광 정보 입력
n, m = map(int, input().split())
array = list(map(int, input().split()))
# 다이나믹 프로그래밍을 위한 2차원 DP 테이블 초기화
dp = []
index = 0
for i in range(n):
dp.append(array[index:index + m])
index += m
# 다이나믹 프로그래밍 진행
for j in range(1, m):
for i in range(n):
# 왼쪽 위에서 오는 경우
if i == 0:
left_up = 0
else:
left_up = dp[i - 1][j - 1]
# 왼쪽 아래에서 오는 경우
if i == n - 1:
left_down = 0
else:
left_down = dp[i + 1][j - 1]
# 왼쪽에서 오는 경우
left = dp[i][j - 1]
dp[i][j] = dp[i][j] + max(left_up, left_down, left)
result = 0
for i in range(n):
result = max(result, dp[i][m - 1])
print(result)
n = int(input())
dp = [] # 다이나믹 프로그래밍을 위한 DP 테이블 초기화
for _ in range(n):
dp.append(list(map(int, input().split())))
# 다이나믹 프로그래밍으로 2번째 줄부터 내려가면서 확인
for i in range(1, n):
for j in range(i + 1):
# 왼쪽 위에서 내려오는 경우
if j == 0:
up_left = 0
else:
up_left = dp[i - 1][j - 1]
# 바로 위에서 내려오는 경우
if j == i:
up = 0
else:
up = dp[i - 1][j]
# 최대 합을 저장
dp[i][j] = dp[i][j] + max(up_left, up)
print(max(dp[n - 1]))
n = int(input()) # 전체 상담 개수
t = [] # 각 상담을 완료하는데 걸리는 기간
p = [] # 각 상담을 완료했을 때 받을 수 있는 금액
dp = [0] * (n + 1) # 다이나믹 프로그래밍을 위한 1차원 DP 테이블 초기화
max_value = 0
for _ in range(n):
x, y = map(int, input().split())
t.append(x)
p.append(y)
# 리스트를 뒤에서부터 거꾸로 확인
for i in range(n - 1, -1, -1):
time = t[i] + i
# 상담이 기간 안에 끝나는 경우
if time <= n:
# 점화식에 맞게, 현재까지의 최고 이익 계산
dp[i] = max(p[i] + dp[time], max_value)
max_value = dp[i]
# 상담이 기간을 벗어나는 경우
else:
dp[i] = max_value
print(max_value)
n = int(input())
array = list(map(int, input().split()))
# 순서를 뒤집어 '최장 증가 부분 수열' 문제로 변환
array.reverse()
# 다이나믹 프로그래밍을 위한 1차원 DP 테이블 초기화
dp = [1] * n
# 가장 긴 증가하는 부분 수열(LIS) 알고리즘 수행
for i in range(1, n):
for j in range(0, i):
if array[j] < array[i]:
dp[i] = max(dp[i], dp[j] + 1)
# 열외해야 하는 병사의 최소 수를 출력
print(n - max(dp))
못생긴 수
A. 문제 못생긴 수란 오직 2, 3, 5만을 소인수로 가지는 수를 의미한다. 다시 말해 오직 2, 3, 5를 약수로 가지는 합성수를 의미한다. 1은 못생긴 수라고 가정한다. 따라서 못생긴 수들은 {1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15 ...} 순으로 이어지게 된다. 이때, n번째 못생긴 수를 찾는 프로그램을 작성하세요. a. 예를 들면. 11번째 못생긴 수는 15입니다. b. 입력 조건 첫째 줄에 n이 입력됩니다.1 <= n <= 1,000 c. 출력 조건 n번째 못생긴 수를 출력한다.
n = int(input())
ugly = [0] * n # 못생긴 수를 담기 위한 테이블 (1차원 DP 테이블)
ugly[0] = 1 # 첫 번째 못생긴 수는 1
# 2배, 3배, 5배를 위한 인덱스
i2 = i3 = i5 = 0
# 처음에 곱셈 값을 초기화
next2, next3, next5 = 2, 3, 5
# 1부터 n까지의 못생긴 수들을 찾기
for l in range(1, n):
# 가능한 곱셈 결과 중에서 가장 작은 수를 선택
ugly[l] = min(next2, next3, next5)
# 인덱스에 따라서 곱셈 결과를 증가
if ugly[l] == next2:
i2 += 1
next2 = ugly[i2] * 2
if ugly[l] == next3:
i3 += 1
next3 = ugly[i3] * 3
if ugly[l] == next5:
i5 += 1
next5 = ugly[i5] * 5
# n번째 못생긴 수를 출력
print(ugly[n - 1])
편집 거리
A. 문제 두 개의 문자열 A, B가 주어졌을 때, 문자열 A를 편집하여 문자열 B로 만들고자 합니다. 문자열 A를 편집할 때는 다음의 세 연산 중에서 한 번에 하나씩 선택하여 이용할 수 있다. 삽입 (Insert)특정한 위치에 하나의 문자를 삽입한다.삭제 (Remove)특정한 위치에 있는 하나의 문자를 삭제한다.교체 (Replace)특정한 위치에 있는 하나의 문자를 다른 문자로 교체한다. 편집 거리란 문자열 A를 편집하여 문자열 B로 만들기 위해 사용한 연산의 수를 의미한다. 문자열 A를 문자열 B로 만드는 최소 편집 거리를 계산하는 프로그램을 작성하라. a. 예를 들면. sunday와 saturday의 최소 편집 거리는 3이다. b. 입력 조건 두 문자열 A, B가 한 줄에 하나씩 주어진다.각 문자열은 영문 알파벳으로만 구성되어 있으며, 각 문자열의 길이는 1보다 크거나 같고, 5,000보다 작거나 같다. c. 출력 조건 최소 편집 거리를 출력한다.
# 최소 편집 거리(Edit Distance) 계산을 위한 다이나믹 프로그래밍
def edit_dist(str1, str2):
n = len(str1)
m = len(str2)
# 다이나믹 프로그래밍을 위한 2차원 DP 테이블 초기화
dp = [[0] * (m + 1) for _ in range(n + 1)]
# DP 테이블 초기 설정
for i in range(1, n + 1):
dp[i][0] = i
for j in range(1, m + 1):
dp[0][j] = j
# 최소 편집 거리 계산
for i in range(1, n + 1):
for j in range(1, m + 1):
# 문자가 같다면, 왼쪽 위에 해당하는 수를 그대로 대입
if str1[i - 1] == str2[j - 1]:
dp[i][j] = dp[i - 1][j - 1]
# 문자가 다르다면, 세 가지 경우 중에서 최솟값 찾기
else: # 삽입(왼쪽), 삭제(위쪽), 교체(왼쪽 위) 중에서 최소 비용을 찾아 대입
dp[i][j] = 1 + min(dp[i][j - 1], dp[i - 1][j], dp[i - 1][j - 1])
return dp[n][m]
# 두 문자열을 입력 받기
str1 = input()
str2 = input()
# 최소 편집 거리 출력
print(edit_dist(str1, str2))
댓글