Problem Solving/[ν•­ν•΄99] TIL

99클럽 μ½”ν…Œ μŠ€ν„°λ”” 22일차 TIL / 완전탐색

geum 2024. 11. 18. 23:03

✏️ 문제

[ν”„λ‘œκ·Έλž˜λ¨ΈμŠ€/Programmers] ν”Όλ‘œλ„(https://school.programmers.co.kr/learn/courses/30/lessons/87946)

 

XXκ²Œμž„μ—λŠ” ν”Όλ‘œλ„ μ‹œμŠ€ν…œ(0 μ΄μƒμ˜ μ •μˆ˜λ‘œ ν‘œν˜„ν•©λ‹ˆλ‹€)이 있으며, 일정 ν”Όλ‘œλ„λ₯Ό μ‚¬μš©ν•΄μ„œ λ˜μ „μ„ νƒν—˜ν•  수 μžˆμŠ΅λ‹ˆλ‹€. μ΄λ•Œ, 각 λ˜μ „λ§ˆλ‹€ νƒν—˜μ„ μ‹œμž‘ν•˜κΈ° μœ„ν•΄ ν•„μš”ν•œ "μ΅œμ†Œ ν•„μš” ν”Όλ‘œλ„"와 λ˜μ „ νƒν—˜μ„ λ§ˆμ³€μ„ λ•Œ μ†Œλͺ¨λ˜λŠ” "μ†Œλͺ¨ ν”Όλ‘œλ„"κ°€ μžˆμŠ΅λ‹ˆλ‹€. "μ΅œμ†Œ ν•„μš” ν”Όλ‘œλ„"λŠ” ν•΄λ‹Ή λ˜μ „μ„ νƒν—˜ν•˜κΈ° μœ„ν•΄ 가지고 μžˆμ–΄μ•Ό ν•˜λŠ” μ΅œμ†Œν•œμ˜ ν”Όλ‘œλ„λ₯Ό λ‚˜νƒ€λ‚΄λ©°, "μ†Œλͺ¨ ν”Όλ‘œλ„"λŠ” λ˜μ „μ„ νƒν—˜ν•œ ν›„ μ†Œλͺ¨λ˜λŠ” ν”Όλ‘œλ„λ₯Ό λ‚˜νƒ€λƒ…λ‹ˆλ‹€. 예λ₯Ό λ“€μ–΄ "μ΅œμ†Œ ν•„μš” ν”Όλ‘œλ„"κ°€ 80, "μ†Œλͺ¨ ν”Όλ‘œλ„"κ°€ 20인 λ˜μ „μ„ νƒν—˜ν•˜κΈ° μœ„ν•΄μ„œλŠ” μœ μ €μ˜ ν˜„μž¬ 남은 ν”Όλ‘œλ„λŠ” 80 이상 이어야 ν•˜λ©°, λ˜μ „μ„ νƒν—˜ν•œ ν›„μ—λŠ” ν”Όλ‘œλ„ 20이 μ†Œλͺ¨λ©λ‹ˆλ‹€. 이 κ²Œμž„μ—λŠ” ν•˜λ£¨μ— ν•œ λ²ˆμ”© νƒν—˜ν•  수 μžˆλŠ” λ˜μ „μ΄ μ—¬λŸ¬κ°œ μžˆλŠ”λ°, ν•œ μœ μ €κ°€ 였늘 이 λ˜μ „λ“€μ„ μ΅œλŒ€ν•œ 많이 νƒν—˜ν•˜λ € ν•©λ‹ˆλ‹€. μœ μ €μ˜ ν˜„μž¬ ν”Όλ‘œλ„ k와 각 λ˜μ „λ³„ "μ΅œμ†Œ ν•„μš” ν”Όλ‘œλ„", "μ†Œλͺ¨ ν”Όλ‘œλ„"κ°€ λ‹΄κΈ΄ 2차원 λ°°μ—΄ dungeons κ°€ λ§€κ°œλ³€μˆ˜λ‘œ μ£Όμ–΄μ§ˆ λ•Œ, μœ μ €κ°€ νƒν—˜ν• μˆ˜ μžˆλŠ” μ΅œλŒ€ λ˜μ „ 수λ₯Ό return ν•˜λ„λ‘ solution ν•¨μˆ˜λ₯Ό μ™„μ„±ν•΄μ£Όμ„Έμš”.

 

μ œν•œμ‚¬ν•­

  • kλŠ” 1 이상 5,000 μ΄ν•˜μΈ μžμ—°μˆ˜μž…λ‹ˆλ‹€.
  • dungeons의 μ„Έλ‘œ(ν–‰) 길이(즉, λ˜μ „μ˜ 개수)λŠ” 1 이상 8 μ΄ν•˜μž…λ‹ˆλ‹€.
  • dungeons의 κ°€λ‘œ(μ—΄) κΈΈμ΄λŠ” 2 μž…λ‹ˆλ‹€.
  • dungeons의 각 행은 각 λ˜μ „μ˜ ["μ΅œμ†Œ ν•„μš” ν”Όλ‘œλ„", "μ†Œλͺ¨ ν”Όλ‘œλ„"] μž…λ‹ˆλ‹€. "μ΅œμ†Œ ν•„μš” ν”Όλ‘œλ„"λŠ” 항상 "μ†Œλͺ¨ ν”Όλ‘œλ„"보닀 ν¬κ±°λ‚˜ κ°™μŠ΅λ‹ˆλ‹€.
  • "μ΅œμ†Œ ν•„μš” ν”Όλ‘œλ„"와 "μ†Œλͺ¨ ν”Όλ‘œλ„"λŠ” 1 이상 1,000 μ΄ν•˜μΈ μžμ—°μˆ˜μž…λ‹ˆλ‹€.
  • μ„œλ‘œ λ‹€λ₯Έ λ˜μ „μ˜ ["μ΅œμ†Œ ν•„μš” ν”Όλ‘œλ„", "μ†Œλͺ¨ ν”Όλ‘œλ„"]κ°€ μ„œλ‘œ 같을 수 μžˆμŠ΅λ‹ˆλ‹€.

 

πŸ€– μž…μΆœλ ₯ μ˜ˆμ‹œ

 

🧐 λ‚œμ΄λ„/μ†Œμš” μ‹œκ°„

βœ… λ‚œμ΄λ„: ν”„λ‘œκ·Έλž˜λ¨ΈμŠ€ Level.2

βœ… μ†Œμš” μ‹œκ°„: 53λΆ„

βœ… ꢌμž₯ μ‹œκ°„: 1μ‹œκ°„ 15λΆ„

 

πŸ’‘ 풀이

1) 문제 이해

λ¬Έμ œμ— μ νžŒλŒ€λ‘œ μ­‰ κ΅¬ν˜„ν•˜λ©΄ λ˜λŠ” λ¬Έμ œλ‹€. λ¬Έμ œμ—μ„œ 주어진 μ΅œλŒ€ 개수의 λ˜μ „μ΄ μž…λ ₯으둜 λ“€μ–΄μ˜¨λ‹€κ³  해도 전체 4만 개 μ •λ„λ§Œ ν™•μΈν•˜λ©΄ 되기 λ•Œλ¬Έμ— μ›¬λ§Œν•˜λ©΄ μ‹œκ°„ μ΄ˆκ³Όκ°€ μ•ˆ λ‚˜μ§€ μ•Šμ„κΉŒ μ‹Άλ‹€.

 

λ˜μ „ λ°©λ¬Έ μˆœμ„œλ₯Ό 미리 λ§Œλ“€μ–΄λ‘κ³ , 각 μˆœμ„œλ§ˆλ‹€ λ°©λ¬Έ κ°€λŠ₯ν•œ λ˜μ „ 개수λ₯Ό μ²΄ν¬ν•˜κΈ° μœ„ν•΄ itertools λͺ¨λ“ˆμ˜ permutations ν•¨μˆ˜λ₯Ό μ‚¬μš©ν–ˆλ‹€.

 

2) 아이디어 흐름

β‘  μ •λ‹΅ μ €μž₯ λ³€μˆ˜ answer μ΄ˆκΈ°κ°’μ„ -1둜 μ„€μ •

 

β‘‘ λ˜μ „ λ°©λ¬Έ μˆœμ„œ 미리 λ§Œλ“€μ–΄λ‘κΈ°

→ dungeon_combinations = list(permutations(dungeons, len(dungeons)))

 

β‘’ dungeon_combinations 리슀트λ₯Ό μˆœνšŒν•˜λ©΄μ„œ λ°©λ¬Έ μˆœμ„œ 확인

→ current_order = ν˜„μž¬ 확인 쀑인 λ°©λ¬Έ μˆœμ„œ 리슀트

for i in range(0, len(dungeon_combinations)):
        current_order = dungeon_combinations[i]

 

β‘£ current_orderλ₯Ό 주어진 λ˜μ „ 개수만큼 μˆœνšŒν•˜λ©΄μ„œ μ΅œμ†Œ ν•„μš” ν”Όλ‘œλ„μ™€ μ†Œλͺ¨ ν”Όλ‘œλ„λ₯Ό 가지고 남은 ν”Όλ‘œλ„ 계산

 

β‘€ 남은 ν”Όλ‘œλ„κ°€ ν˜„μž¬ λ°©λ¬Έν•œ λ˜μ „μ˜ μ΅œμ†Œ ν•„μš” ν”Όλ‘œλ„λ³΄λ‹€ μž‘μœΌλ©΄ 더이상 νƒμƒ‰ν•˜μ§€ μ•Šκ³  λ‹€μŒ λ°©λ¬Έ μˆœμ„œ 리슀트 확인

 

3) κ΅¬ν˜„

from itertools import permutations

def solution(k, dungeons):
    answer = -1
    
    dungeon_combinations = list(permutations(dungeons, len(dungeons)))

    dungeon_len = len(dungeons)
    
    for i in range(0, len(dungeon_combinations)):
        visit_cnt = 0
        
        current_order = dungeon_combinations[i]
        
        fatigue = k
        
        for j in range(0, dungeon_len):
            if fatigue >= current_order[j][0]:
                visit_cnt += 1
                
                fatigue -= current_order[j][1]
                
                answer = max(answer, visit_cnt)
            else:
                break
                
    return answer

 

4) μ–΄λ €μ› λ˜ 점/배운 μ 

🚨 μ–΄λ €μ› λ˜ 점

  • μ—†μŒ

❗ 배운 점

  • λ³€μˆ˜ μ„ μ–Έ μœ„μΉ˜κ°€ 맀우맀우 μ€‘μš”ν•¨ - μ²˜μŒμ— answer = max(answer, visit_cnt) 뢀뢄을 λ‹€λ₯Έ 곳에 λ„£μ–΄λ‘¬μ„œ 닡이 μ œλŒ€λ‘œ λ‚˜μ˜€μ§€ μ•Šμ•˜λ‹€.

 

μ €μž‘μžν‘œμ‹œ λΉ„μ˜λ¦¬ λ³€κ²½κΈˆμ§€ (μƒˆμ°½μ—΄λ¦Ό)