33_퇴사

2024. 2. 14. 16:39· 알고리즘/이것이 코딩테스트다
728x90
 

14501번: 퇴사

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

www.acmicpc.net

 

DP 문제다.

상담을 진행했을 때, 받을 수 있는 최대 이익을 출력하면 되는 문제.

 

처음에 그냥 떠오른 점화식은 다음과 같다.

time와 price 리스트가 있을 때, 

dp[i+time[i]] = max(dp[i] + price[i], dp[i+time[i])

 

이런 식으로 점화식을 만들어주면, 답이 나오는 것 같았다.

물론 돌려보니 실패했다.

반례를 찾다보니, 통과하지 못하는 반례르 발견했다.

 

4

3 1

1 100

2 100

1 1000

 

이 반례의 정답은 1100인데 1001이라는 잘못된 답을 뱉어냈다.

 

dp테이블을 손수 직접 돌아보면서, 잘못된 점을 찾았고, 새로운 점화식을 만들었다.

dp[i+time[i]] = max(max(dp[:i+1]) + price[i], dp[i+time[i]])

 

dp[i] = i-1번째 날짜까지 상담을 진행한 후, 이익의 최댓값

즉, dp[8]은 7번째 날짜까지 상담을 진행한 후, 이익의 최댓값을 의미한다.

 

이 점화식에서 바뀐 부분은 굵게 표시된 부분이다.

위 부분을 바꾼 이유는 dp 테이블을 갱신하다가 만약 특정 날짜의 dp테이블을 확인했을 때, 0인 경우도 존재하고, 

또한 0이 아니더라도, 그 동안 만든 dp 테이블의 최댓값에다가 그날 상담을 진행할 경우, 얻을 수 있는 이익을 더하는 것이 맞다.

 

즉,

dp[i+time[i]] = (i - 1)+time[i]번째 날까지 상담을 진행한 후의 최대 이익

max(dp[:i+1]) + price[i] = i-1번째 날까지의 최대이익 + i번째 날 상담을 진행할 경우 얻는 이익

이 2가지를 비교해서 더 큰 값을 dp[i+time[i]]에 갱신해준다.

 

 

풀이 코드

# 14501번: 퇴사

n = int(input())
time = [0] # 상담하는데 필요한 기간
price = [0] # 상담 이익

dp = [0] * 21 # dp 테이블

# 상담기간, 상담이익 추가
for _ in range(n):
    t, p = map(int, input().split())
    time.append(t)
    price.append(p)


# dp 테이블 갱신
for i in range(1, n+1):
    dp[i+time[i]] = max(max(dp[:i+1])+price[i], dp[i+time[i]])

# print(dp[1:])
print(max(dp[:n+2]))

 


다른 풀이

 

책에서는 약간 다르게 풀었다.

dp 테이블을 갱신할 때, 뒤쪽 날짜부터 거꾸로 확인하는 방식으로 접근하여 해결하는 것이다.

 

위 백준 링크에 첫번째 예시의 경우를 보자.

만약 1일차에 상담을 진행한다고 하자.

이 경우 3일에 걸쳐서 상담을 진행해야 하므로 결과적으로 4일부터 상담을 진행할 수 있다.

그러므로 1일차에 상담을 진행할 경우 얻을 수 있는 최대 이익은 "1일차의 상담 금액 + 4일부터의 최대 상금 금액"이다.

이러한 원리를 이용해, 뒤쪽부터 거꾸로 계산해서 문제를 해결할 수 있다.

 

뒤쪽부터, 매 상담에 대해 

현재 상담 금액 -> p[i]

현재 상담을 마친 일자부터의 최대 이윤 -> dp[i+time[i]]

를 더한 값을 계산하면 된다.

이후에 계산된 각각의 값 중에서 최댓값을 출력하면 된다.

 

여기서 dp[i]는 i번째 날부터 마지막 날까지 낼 수 있는 최대 이익이다.

 

점화식은 다음과 같다.

dp[i] = max(dp[i + time[i]) + price[i], max_value)

 

이때, max_value는 뒤에서부터 계산할 때, 현재까지의 최대 상담 금액에 해당하는 변수다.

 

 

풀이 코드

# 14501번: 퇴사

# 풀이 2.
n = int(input())
time = [] # 상담하는데 필요한 기간
price = [] # 상담 이익

dp = [0] * 21 # dp 테이블

# 상담기간, 상담이익 추가
for _ in range(n):
    t, p = map(int, input().split())
    time.append(t)
    price.append(p)
max_value = 0

# 리스트를 뒤에서부터 거꾸로 확인
for i in range(n-1, -1, -1):
    t = time[i] + i
    # 상담이 기간 안에 끝나는 경우
    if t <= n:
        # 점화식에 맞게, 현재까지의 최고 이익 계산
        dp[i] = max(price[i] + dp[t], max_value)
        max_value = dp[i]
    # 상담이 기간을 벗어나는 경우
    else:
        dp[i] = max_value

print(max_value)

 

뒤에서부터 계산한다는 것은 생각하지 못했다.

dp 문제는 이런 방식으로도 풀 수 있다는 것을 알았던 문제였다.

728x90

'알고리즘 > 이것이 코딩테스트다' 카테고리의 다른 글

35_못생긴 수  (0) 2024.02.15
34_병사 배치하기  (0) 2024.02.15
32_정수 삼각형  (0) 2024.02.14
31_금광  (1) 2024.02.14
30_가사 검색  (0) 2024.02.13
'알고리즘/이것이 코딩테스트다' 카테고리의 다른 글
  • 35_못생긴 수
  • 34_병사 배치하기
  • 32_정수 삼각형
  • 31_금광
happenundo
happenundo
happenundo
2023~ 개발블로그
happenundo
전체
오늘
어제
  • 분류 전체보기 (207)
    • TIL (3)
    • 알고리즘 (188)
      • 프로그래머스 (47)
      • 백준 (69)
      • 파이썬 문법 (11)
      • 이것이 코딩테스트다 (46)
      • 알고리즘 노트 (6)
      • SQL (8)
    • Spring (4)
      • Spring 입문 (2)
      • 개인 프로젝트 (1)
      • 인텔리제이 (1)
    • CS (8)
      • DB (2)
      • 네트워크 (1)
      • 그외 (5)
    • ~2022 (1)
    • etc (2)

블로그 메뉴

  • 홈
  • 태그
  • 방명록

공지사항

인기 글

태그

  • 이코테
  • 완전탐색
  • 우선순위큐
  • 파이썬
  • 플로이드워셜
  • 알고리즘
  • 다익스트라
  • deepcopy
  • dfs
  • distinct
  • 백트래킹
  • 괄호변환
  • 정렬
  • 백준
  • 최단거리
  • 재귀
  • 큐
  • 동적프로그래밍
  • 스택
  • DP
  • BinarySearch
  • 다이나믹프로그래밍
  • 그리디
  • 프로그래머스
  • CS
  • 이것이코딩테스트다
  • 이진탐색
  • sql
  • BFS
  • 구현

최근 댓글

최근 글

hELLO · Designed By 정상우.v4.2.2
happenundo
33_퇴사
상단으로

티스토리툴바

단축키

내 블로그

내 블로그 - 관리자 홈 전환
Q
Q
새 글 쓰기
W
W

블로그 게시글

글 수정 (권한 있는 경우)
E
E
댓글 영역으로 이동
C
C

모든 영역

이 페이지의 URL 복사
S
S
맨 위로 이동
T
T
티스토리 홈 이동
H
H
단축키 안내
Shift + /
⇧ + /

* 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.