1. 1로만들기

정수 X가 주어질 때 (1<= X <= 30,000) 다음과 같은 연산으로 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오.

• X가 5로 나누어떨어지면 5로 나눈다.
• X가 3로 나누어떨어지면 3로 나눈다.
• X가 2로 나누어떨어지면 2로 나눈다.
• X에서 1을 뺀다.

1.1 내 답안

• 1빼는 연산은 최대 2번까지 고려했는데 1번까지만 해도 됨. (2로 나누는 연산 때문이 아님)

x = int(input())
d = [0]*30001
d[2],d[3],d[5] = 1,1,1

def abcd(x, d):
  count_list = []
  count = 1 # 연산 횟수 
  for i in range(x,x-3,-1):
    if i%5 == 0:
      count_list.append(count+d[i//5])
    elif i%3 == 0:
      count_list.append(count+d[i//3])
    elif i%2 == 0:
      count_list.append(count+d[i//2])
    count += 1 # 다음 단계는 (-1) 연산 추가됨
  return min(count_list)

for i in range(2,x+1):
  if d[i] != 0:
    continue
  else:
    d[i] = abcd(i, d)

print(d[x])
  

1.2 책 답안

• 선택정렬처럼 min 함수로 바로 비교하기
• 연산의 순서에서 우선순위는 딱히 없음. (5먼저확인 > 3확인> 2확인.. 하지 않아도 됨) 다이나믹 프로그래밍이 유용한 부분.

 
x = int(input())

# 앞서 계산된 결과를 저장하기 위한 DP 테이블 초기화
d = [0]*30001

# 다이나믹 프로그래밍, 보텀업
for i in range(2, x+1):
  # 현재의 수에서 1을 빼는 경우 
  d[i] = d[i-1]+1

  if i%2 == 0:
    d[i] = min(d[i], d[i//2]+1)
  if i%3 == 0:
    d[i] = min(d[i], d[i//3]+1)
  if i%5 == 0:
    d[i] = min(d[i], d[i//5]+1)
print(d[x])

2. 개미 전사

• 첫째 줄에 식량창고의 개수 N이 주어진다. (3<= N <= 100)
• 둘째 줄에 공백으로 구분되어 각 식량창고에 저장된 식량의 개수 K 가 주어진다. (0<= K <= 1,000)
• 이웃한 식량창고는 동시에 선택할 수 없을 때, 선택하는 식량 합의 최댓값은?

2.1 내 코드

• i번째 식량창고에 대한 최적의 해를 구할 때 왼쪽부터 (i-3)번 째 이하의 식량 창고에 대한 최적해에 대해선 고려할 필요가 없는데
  • 나는 i-3번째 식량 선택하면 i번째 식량은 반드시 선택해야한다고 생각함(식량 합이 최대가 되도록 선택하기 위해선 그래야 하긴 함.)
  • 근데 i-3번째의 경우, i-1번째와 i-2번째를 구하는 과정에서 이미 계산된다.

n = int(input())
k = list(map(int, input().split()))

array = [[2], [1,3]] # n=3일 때 가능한 많은 식량을 얻는 인덱스 경우
for i in range(4, n+1):
  array1 = [x for x in array if x[-1]==i-1 or x[-1]==i-2]
  array2 = [x+[i] for x in array if x[-1]==i-2 or x[-1]==i-3]
  array = array1 + array2

def cal(num_list,index_list): 
  sum = 0
  for x in index_list:
    sum += num_list[x-1]
  return sum

result = 0 
for list in array:
  result = max(result,cal(k, list))
print(result)
  

2.2 책 답안

• 나는 점화식 찾지 못하고 모든 경우의 수 고려했음(최댓값을 구하는 게 목적이었으므로 n=i 일 때 인덱스 선택 후보가 i-1개여서 간단했음)
• 점화식을 찾고 초기값 설정하기

n = int(input())
array = list(map(int, input().split()))

#앞서 계산된 결과를 저장하기 위한 DP 테이블 초기화
d=[0]*100

# 다이나믹 프로그래밍 진행 (보텀업)
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])

3. 바닥공사

• 가로 x 세로= (Nx2)인 직사각형 형태의 바닥이 있다. (1<= N<= 1,000)
• 이 바닥을 (1x2)의 덮개, (2x1)의 덮개, (2x2)의 덮개를 이용해 채우려고 할 때
• 바닥을 채우는 모든 경우의 수는?

3.1 내 답안

n = int(input())
# f(x+2) = f(x+1) + f(x)*2

d = [0]*1001
d[1] = 1
d[2] = 3
for i in range(1,n+1):
  if d[i] != 0:
    continue
  else:
    d[i] = (d[i-1] + d[i-2]*2)%796796

print(d[n])

3.2 책 답안

n = int(input())

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

print(d[n])

4. 효율적인 화폐 구성

• 첫째 줄에 화폐 단위 종류 N(가지)와 총 금액 M(원)을 입력 (1<=N<=100)(1<=M<=10,000)
• 이후 N개의 줄에는 각 화폐 단위가 주어짐. (화폐 단위는 10,000 이하 자연수)

출력조건 : M원을 만들기 위한 최소한의 화폐 개수, 만약 불가능할 때는 -1 출력

4.1 내 답안

• 나는 d[i+k] = min(d[i+k], d[i]+1) 방향으로 했는데, 책에선 d[j] = min(d[j-k]+1, d[j]) 방향으로 함.
• 초기값 0 대신 10001같이 큰 수로 설정했다면 개수가 기록되기 전/후 조건문 안 써도 됐을것.

n, m = map(int, input().split())

d = [0]*10001
coin= []

for i in range(n):
  x = int(input())
  if x <= m: # m이하 화폐단위만 coin에 기록
    coin.append(x)
    d[x] = 1

for i in range(m+1):
  if d[i] != 0:
    for x in coin:
      if d[i+x] == 0: # 개수가 기록되기 전
        d[i+x] = d[i]+1
      else: # 개수 기록되어 있을 때
        d[i+x] = min(d[i+x], d[i]+1)

if d[m] != 0:
  print(d[m])
else:
  print(-1)

4.2 책 답안

• 점화식
  • a_i-k 를 만드는 방법이 존재하는 경우 : a_i = min(a_i, a_i-k +1)
  • a_i-k 를 만드는 방법이 존재하지 않는 경우 : a_i = 10001
• if d[j-array[i]] != 10001은 생략해도 됨. d[j-array[i]]가 10001값을 가지더라도 min함수 통과해서 d[j]가 나올 것이므로

n, m = map(int, input().split())

array = []
for i in range(n):
  array.append(int(input()))

# 한 번 계산된 결과를 저장하기 위한 dp 테이블 초기화(초기화 값 : 10001)
d = [10001]*(m+1) 

d[0] = 0 # 화폐를 하나도 사용하지 않았을 때 만들 수 있으므로 값으로 0을 설정

for i in range(n):
  for j in range(array[i], m+1):
    if d[j-array[i]] != 10001: #(i-array[i])원 만드는 방법이 존재할 경우
      d[j] = min(d[j-array[i]]+1, d[j])

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