Algorithm Problem/Python

[python] ํ”„๋กœ๊ทธ๋ž˜๋จธ์Šค - ํ”ผ๋กœ๋„(์œ„ํด๋ฆฌ์ฑŒ๋ฆฐ์ง€)

deo2kim 2022. 2. 4. 19:53
๋ฐ˜์‘ํ˜•

๐Ÿค”๋ฌธ์ œ ํ•ด๊ฒฐ

๐Ÿ’ซ ๋˜์ „์˜ ๊ธธ์ด๊ฐ€ ์ตœ๋Œ€ 8๊ฐœ ์ด๋ฏ€๋กœ permutation์œผ๋กœ ํƒํ—˜ํ•˜๋Š” ์ˆœ์„œ์˜ ๋ชจ๋“  ๊ฒฝ์šฐ์˜ ์ˆ˜๋ฅผ ๊ตฌํ–ˆ๋‹ค.

๐Ÿ’ซ ํƒํ—˜ ์ˆœ์„œ๋Œ€๋กœ ๋˜์ „์„ ํƒํ—˜ํ•˜๋ฉฐ ํ”ผ๋กœ๋„ ์กฐ๊ฑด์— ๋งž๋Š” ๋™๊ตด๋งŒ ํƒํ—˜ํ•˜๋ฉฐ ๊ฐฏ์ˆ˜๋ฅผ ์„ธ์–ด์ค€๋‹ค.

๐Ÿ’ซ ๊ฐ๊ฐ์˜ ์‚ฌ์ดํด๋งˆ๋‹ค ํƒํ—˜๊ฐ€๋Šฅํ•œ ๋™๊ตด์˜ ๊ฐฏ์ˆ˜๋ฅผ ์ตœ๋Œ€๊ฐ’์œผ๋กœ ์—…๋ฐ์ดํŠธ ํ•ด์ค€๋‹ค.

 

๐Ÿ’ป์†Œ์Šค ์ฝ”๋“œ

from itertools import permutations


def solution(k, dungeons):
    answer = -1
    for perm in (permutations(dungeons, len(dungeons))):
        cur_k = k
        expol_cnt = 0
        for dungeon in perm:
            if cur_k >= dungeon[0]:
                expol_cnt += 1
                cur_k -= dungeon[1]

        answer = max(answer, expol_cnt)
    return answer

 

๐Ÿ“•๋ฌธ์ œ ํ™•์ธ

์ถœ์ฒ˜: ํ”„๋กœ๊ทธ๋ž˜๋จธ์Šค

๋งํฌ: ํ”ผ๋กœ๋„

๋ฐ˜์‘ํ˜•