1로 만들기(실버3)
<힌트> 10의 경우에 10 → 9 → 3 → 1 로 3번 만에 만들 수 있다.
다이나믹 프로그래밍 문제로 바텀업 방식을 이용하여 풀었다. 정수N은 1부터 10^6까지 가능하다. 1일 경우 1로 갈 이유가 없으므로 연산횟수는 0회이다. 2일 경우 1로 가는 경우의 수는 딱 한가지 3번의 연산이므로 1이다. 3일 경우 3-1-1, 3/3 이 존재하므로 3/3이 최소 연산 횟수 이므로 1이다. dp의 핵심은 중복연산의 제거이다.
1부터 N-1까지 숫자에 대하여 최소 연산 횟수를 모두 메모리에 기억하고 있다고 가정해보자. 우리는 N에 대한 최소 연산 횟수를 알고 싶을 때 우선 N이 -1, %2, %3 연산이 되는 지 확인한다. 만약 모두 가능한 숫자인 24를 가지고 생각해보자. 24가 한번의 연산으로 다음의 세 수가 될 수 있다. 23, 12, 8 우리는 여기서 1부터 N-1까지 숫자에 대해 최소 연산 횟수를 모두 기억하고 있기에 23, 12, 8에서 누가 최솟값을 가지는 지 보면 된다. 만약 그것이 8이라고 가정해보자. 그럼 우리는 24에 dp[8]+1(한번 연산한 거 추가해주기)를 저장하게 된다.
그렇게 N이 주어졌다면 1부터 dp리스트에 최소연산횟수를 계속해서 쌓아간 후 N에 대한 최소연산 횟수를 구하면 된다.
n = int(input())
def solution(num):
dp = [0]*(num+5)
dp[0] = 0 # 안씀
dp[1] = 0 # 1이 1이 되는 최소 계산횟수 = 0회
dp[2] = 1 # 2가 1이 되는 최소 계산횟수 = 1회
if num < 3:
return dp[num]
for i in range(3, num+1):
field = []
field.append(dp[i-1] + 1)
if i % 2 == 0:
field.append(dp[i//2]+1)
if i % 3 == 0:
field.append(dp[i//3]+1)
if i % 6 == 0:
field.append(dp[i//6]+2)
dp[i] = min(field)
return dp[num]
print(solution(n)) 1,2,3 더하기(실버3)
정수 4에 대한 풀이를 메모장에 직접 써서 어떻게 풀지 감을 얻었다.
첫번째, 연산 이전의 경우의 수를 적는다.
두번째, 1,2,3에 대해 4보다 크지 않게 경우의 수를 모두 적는다. 4가 넘는다면 그냥 적지 않는다.
세번째, 두번째에서 만들어진 4들을 빼고 두번째를 반복한다.
네번째, 동일
저기서 보이는 4를 모두 카운트 해주면 된다.
N = int(input())
def get_dp(dp, N):
new_dp = []
for i in dp:
if i + 1 <= N:
new_dp.append(i + 1)
if i + 2 <= N:
new_dp.append(i + 2)
if i + 3 <= N:
new_dp.append(i + 3)
return new_dp
def count_f(dp, N):
count = 0
new_dp = []
for i in dp:
if i == N:
count += 1
else:
new_dp.append(i)
return count, new_dp
def solution(N):
new_dp = [1, 2, 3]
count_ = 0
if N == 1:
return 1
if N == 2:
return 2
if N == 3:
return 4
while len(new_dp) != 0:
new_dp = get_dp(new_dp, N)
count, new_dp = count_f(new_dp, N)
count_ += count
return count_
for i in range(N):
n_ = int(input())
print(solution(n_))헷갈리기 싫어서 모듈화 해서 진행했다. get_dp의 경우 이전 숫자 조합을 통해 새로운(다음단계) 숫자조합을 만들어 준다. count_f의 경우 목표한 N에 도달한 경우를 지우고 해당 경우를 카운트 한다.(두 개의 리턴을 줌)
그리고 dp의 길이가 0이 될때까지 이 과정을 무한 반복한다. 쌓은 count를 리턴하는 것이 최종목적이다.
new_dp가 1,2,3으로 초기화되기 때문에 N = 1, 2, 3일 경우는 따로 암산해서 구겨넣었다.
퇴사 2
굉장히 복잡해보인다. DP문제로 알고 풀지만, 먼저 브루트하게 접근해보는 것이 바람직하다. 구하려는 것은 퇴사직전까지 일하는 일 수에 상관 없이 최대한의 페이를 가져가는 것이다 우선 예시의 모든 예시를 작성해본다. 1일에 일할 경우부터 해서 돈에 상관없이 일을 하는 경우를 쭉 나열 해볼 경우
1일, 1일-4일-5일, 1일-4일, 1일-5일
2일
3일, 3일-4일, 3일 5일, 3일-4일-5일
4일, 4일-5일
여기서 중복을 어떻게 제거해야할까 생각해야한다. 우선 다시 생각할 것은 우리는 N일 동안의 일정동안 최대한 많은 페이를 가져가겠다는 것이다. 최종목적의 그 전 단계를 고려해보는 규칙을 적용해보면 만약 7일때에 최대의 페이를 가져가기 위해, 우리는 6일 일정을 고려할 필요는 없다. 6일 일정은 4일짜리 일정이기 때문이다. 5일의 일정은 정확히 N=7일때 정산이 가능하기에 5일의 일정(5일에 시작하는 2일짜리 pay=15)인 경우를 고려해본다. 그렇다면 5일의 일정을 한다고 결정했을 때, 1~4일까지는 최고 페이를 받을 수 있도록 일했다는 뜻이다. 근데 여기서 반례를 하나 넣어서 상상한다. 만약 1일 일정이 Ti가 7일짜리인데 페이가 10^6라면 1~4일까지는 최고페이를 받을 수 있도록 일한 것이 의미가 없어진다. 1일 일정은 N=7일때만 활성화가 되니까. 여기서 우선순위가 확정된다. N일 일때의 상황으로 고려하지 않고 주어지는 일정순으로 처리해야 한다.
1일의 일정인 3일짜리 10pay를 처리하고 가야한다. 1일 일정은 3일에 페이가 확정된다. 그렇기에 3일의 기대수익은 10이다. 2일의 일정인 5일짜리 일정 20pay는 6일에 확정되므로 6일의 기대수익은 1일까지의 기대수익(2일의 전날) + 20pay이다. 그러므로 0+20으로 20이다. 3일의 일정의 경우 1일짜리 일정이므로 2일까지의 번돈 + 3일날 번돈이다. 10이다. 4일의 일정도 동일하게 처리하면 10+20 = 30이 나온다.
5일의 일정을 처리할 때 코딩방향이 나온다. 5일 일정을 처리하기 위해서는 6일에 4일까지 번돈 + 5일일정(15pay) = 45가 나온다. 근데 위의 문단에서 2일의 일정을 확정했을 때 6일의 기대수익은 20이라고 했었다.
1일까지의 max + 2일 일정 = 20
4일까지의 max + 5일 일정 = 45
20을 무시할 수 있다.
여기서 방향이 다이나믹 프로그래밍으로 확정되었다. 우리는 이전의 경우의 수에 대한 값을 미리 저장해놓고 max()계산을 통해 새로운 값에 대한 판단을 해서 업데이트하면 된다.
간단하게 식으로 정리하면,
dp[day+end] = max(dp[day-1] + end_pay, dp[day+end])
from sys import stdin
n = int(stdin.readline())
day_lst = []
pay_lst = []
for i in range(n):
day, pay = map(int, stdin.readline().split())
day_lst.append(day)
pay_lst.append(pay)
dp = [0]*(n+5)
for i in range(n):
day = day_lst[i]
pay = pay_lst[i]
index = i + day - 1
if index < n:
dp[index] = max(dp[index], dp[i-1] + pay)
if dp[i] < dp[i-1]:
dp[i] = dp[i-1]
print(max(dp))
// 오늘은 DP만 //
