J1Yun
ZU-TECHLOG
J1Yun
전체 방문자
였늘
μ–΄μ œ
  • πŸ“‘ Category (135)
    • Algorithm (61)
      • πŸ“š Concept (6)
      • πŸ“˜ Baekjoon Judge (53)
      • πŸ“— Programmers (2)
    • Computer Science (42)
      • πŸ”’ Operating System (14)
      • πŸ“‘ Network (15)
      • πŸ’Ύ Database (8)
      • 🧩 Design Pattern (4)
      • πŸ”‘ Security (1)
    • Activities (12)
      • 🦁 λ©‹μŸμ΄μ‚¬μžμ²˜λŸΌ 9κΈ° (6)
      • πŸ’» SWλ§ˆμ—μŠ€νŠΈλ‘œ 13κΈ° (6)
    • Infra (1)
      • ☁️ AWS (1)
    • Languages (1)
      • πŸ’™ Python (1)
    • Backend (7)
      • πŸ”΅ Django (4)
      • 🟒 Node.js (3)
    • Ect. (8)
      • πŸ’¬ Talk (0)
      • πŸ—‚οΈ 개발직ꡰ μ·¨μ—… μ€€λΉ„μžλ£Œ (8)

λΈ”λ‘œκ·Έ 메뉴

  • ν™ˆ
  • νƒœκ·Έ
  • λ°©λͺ…둝

곡지사항

인기 κΈ€

졜근 λŒ“κΈ€

졜근 κΈ€

ν‹°μŠ€ν† λ¦¬

250x250
hELLO Β· Designed By μ •μƒμš°.
J1Yun

ZU-TECHLOG

[BOJ] λ°±μ€€ 14501번 퇴사 - 파이썬(Python)
Algorithm/πŸ“˜ Baekjoon Judge

[BOJ] λ°±μ€€ 14501번 퇴사 - 파이썬(Python)

728x90

문제

μƒλ‹΄μ›μœΌλ‘œ μΌν•˜κ³  μžˆλŠ” λ°±μ€€μ΄λŠ” 퇴사λ₯Ό ν•˜λ €κ³  ν•œλ‹€.

μ˜€λŠ˜λΆ€ν„° N+1일째 λ˜λŠ” λ‚  퇴사λ₯Ό ν•˜κΈ° μœ„ν•΄μ„œ, 남은 N일 λ™μ•ˆ μ΅œλŒ€ν•œ λ§Žμ€ 상담을 ν•˜λ €κ³  ν•œλ‹€.

λ°±μ€€μ΄λŠ” λΉ„μ„œμ—κ²Œ μ΅œλŒ€ν•œ λ§Žμ€ 상담을 작으라고 뢀탁을 ν–ˆκ³ , λΉ„μ„œλŠ” ν•˜λ£¨μ— ν•˜λ‚˜μ”© μ„œλ‘œ λ‹€λ₯Έ μ‚¬λžŒμ˜ 상담을 μž‘μ•„λ†“μ•˜λ‹€.

각각의 상담은 상담을 μ™„λ£Œν•˜λŠ”λ° κ±Έλ¦¬λŠ” κΈ°κ°„ Ti와 상담을 ν–ˆμ„ λ•Œ 받을 수 μžˆλŠ” κΈˆμ•‘ Pi둜 이루어져 μžˆλ‹€.

N = 7인 κ²½μš°μ— λ‹€μŒκ³Ό 같은 상담 μΌμ •ν‘œλ₯Ό 보자.

 1일2일3일4일5일6일7일TiPi

3 5 1 1 2 4 2
10 20 10 20 15 40 200

1일에 μž‘ν˜€μžˆλŠ” 상담은 총 3일이 걸리며, μƒλ‹΄ν–ˆμ„ λ•Œ 받을 수 μžˆλŠ” κΈˆμ•‘μ€ 10이닀. 5일에 μž‘ν˜€μžˆλŠ” 상담은 총 2일이 걸리며, 받을 수 μžˆλŠ” κΈˆμ•‘μ€ 15이닀.

상담을 ν•˜λŠ”λ° ν•„μš”ν•œ 기간은 1일보닀 클 수 있기 λ•Œλ¬Έμ—, λͺ¨λ“  상담을 ν•  μˆ˜λŠ” μ—†λ‹€. 예λ₯Ό λ“€μ–΄μ„œ 1일에 상담을 ν•˜κ²Œ 되면, 2일, 3일에 μžˆλŠ” 상담은 ν•  수 μ—†κ²Œ λœλ‹€. 2일에 μžˆλŠ” 상담을 ν•˜κ²Œ 되면, 3, 4, 5, 6일에 μž‘ν˜€μžˆλŠ” 상담은 ν•  수 μ—†λ‹€.

λ˜ν•œ, N+1μΌμ§Έμ—λŠ” νšŒμ‚¬μ— μ—†κΈ° λ•Œλ¬Έμ—, 6, 7일에 μžˆλŠ” 상담을 ν•  수 μ—†λ‹€.

퇴사 전에 ν•  수 μžˆλŠ” μƒλ‹΄μ˜ μ΅œλŒ€ 이읡은 1일, 4일, 5일에 μžˆλŠ” 상담을 ν•˜λŠ” 것이며, μ΄λ•Œμ˜ 이읡은 10+20+15=45이닀.

상담을 적절히 ν–ˆμ„ λ•Œ, 백쀀이가 얻을 수 μžˆλŠ” μ΅œλŒ€ μˆ˜μ΅μ„ κ΅¬ν•˜λŠ” ν”„λ‘œκ·Έλž¨μ„ μž‘μ„±ν•˜μ‹œμ˜€.

μž…λ ₯

첫째 쀄에 N (1 ≤ N ≤ 15)이 μ£Όμ–΄μ§„λ‹€.

λ‘˜μ§Έ 쀄뢀터 N개의 쀄에 Ti와 Piκ°€ 곡백으둜 κ΅¬λΆ„λ˜μ–΄μ„œ μ£Όμ–΄μ§€λ©°, 1일뢀터 NμΌκΉŒμ§€ μˆœμ„œλŒ€λ‘œ μ£Όμ–΄μ§„λ‹€. (1 ≤ Ti ≤ 5, 1 ≤ Pi ≤ 1,000)

좜λ ₯

첫째 쀄에 백쀀이가 얻을 수 μžˆλŠ” μ΅œλŒ€ 이읡을 좜λ ₯ν•œλ‹€.

 

https://www.acmicpc.net/problem/14501

 

14501번: 퇴사

첫째 쀄에 백쀀이가 얻을 수 μžˆλŠ” μ΅œλŒ€ 이읡을 좜λ ₯ν•œλ‹€.

www.acmicpc.net

 

πŸ’‘ 풀이 및 μ½”λ“œ

import sys
input = sys.stdin.readline

data = []
n = int(input())
for _ in range(n):
    data.append(list(map(int, input().split())))

d = [0] * (n+1)
for i in range(1,n+1):
    t, p = data[i-1][0], data[i-1][1]
    if i+t-1 <= n:
        d[i+t-1] = max(d[i+t-1], d[i-1] + p)
    if d[i] < d[i-1] :
        d[i] = d[i-1]
print(max(d))

i일째에 μ‹œμž‘ν•œ 상담이 λλ‚˜λŠ” λ‚ (i+t-1)을 κΈ°μ€€μœΌλ‘œ i-1μΌμ§ΈκΉŒμ§€μ˜ μ΅œλŒ€ 상담 λΉ„μš©(d[i-1])에 이번 상담 λΉ„μš©(p)λ₯Ό λ”ν•œ κ°’λ“€ 쀑 κ°€μž₯ 큰 κ°’μœΌλ‘œ DPν…Œμ΄λΈ”(d)을 계속 κ°±μ‹ ν•œλ‹€. μ΄λ•Œ, d[i]κ°€ d[i-1]보닀 μž‘μ„ κ²½μš°λŠ” i-1μΌμ§ΈκΉŒμ§€λ§Œ μƒλ‹΄ν•˜λŠ” 것이 더 μ΄λ“μ΄λ―€λ‘œ d[i]λ₯Ό d[i-1]κ°’μœΌλ‘œ λŒ€μ²΄ν•΄μ€€λ‹€. κ²°κ΅­μ—” DP ν…Œμ΄λΈ”μ˜ μ΅œλŒ“κ°’μ΄ λ°”λ‘œ 백쀀이가 얻을 수 μžˆλŠ” μ΅œλŒ€ 수읡이 λœλ‹€.

 

728x90

'Algorithm > πŸ“˜ Baekjoon Judge' μΉ΄ν…Œκ³ λ¦¬μ˜ λ‹€λ₯Έ κΈ€

[BOJ] λ°±μ€€ 1202번 보석 도둑 - 파이썬(Python)  (0) 2021.11.23
[BOJ] λ°±μ€€ 1012번 μœ κΈ°λ† λ°°μΆ” - 파이썬(Python)  (0) 2021.10.07
[BOJ] λ°±μ€€ 11052번 μΉ΄λ“œ κ΅¬λ§€ν•˜κΈ° - 파이썬(Python)  (0) 2021.10.06
[BOJ] λ°±μ€€ 10844번 μ‰¬μš΄ 계단 수 - 파이썬(Python)  (0) 2021.09.15
[BOJ] λ°±μ€€ 2156번 포도주 μ‹œμ‹ - 파이썬(Python)  (0) 2021.09.15
    'Algorithm/πŸ“˜ Baekjoon Judge' μΉ΄ν…Œκ³ λ¦¬μ˜ λ‹€λ₯Έ 글이닀
    • [BOJ] λ°±μ€€ 1202번 보석 도둑 - 파이썬(Python)
    • [BOJ] λ°±μ€€ 1012번 μœ κΈ°λ† λ°°μΆ” - 파이썬(Python)
    • [BOJ] λ°±μ€€ 11052번 μΉ΄λ“œ κ΅¬λ§€ν•˜κΈ° - 파이썬(Python)
    • [BOJ] λ°±μ€€ 10844번 μ‰¬μš΄ 계단 수 - 파이썬(Python)
    J1Yun
    J1Yun
    개발 κ΄€λ ¨ 기술 및 곡뢀 λ‚΄μš© 기둝μž₯

    ν‹°μŠ€ν† λ¦¬νˆ΄λ°”