프그스_레벨2_피로도 (브루트포스_DFS_고득점 kit_너무쉬웠는데)

RostoryT·2022년 10월 21일
0

Brute force

목록 보기
18/18



메모

  • 필요 피로도

    • 접근할때 필요한 피로도
  • 소모 피로도

    • 탐험 후 차감
  • 하루 한번씩 탐험할 수 있는 던전 여러개

    • 최대한 많이 탐험하려 함
  • k : 현재 유저 피로도

  • [] 묶음

  • output : 유저가 탐험할 수 있는 최대 던전 수

알고리즘 및 방법

  • 걍 permutations 돌려서 모든 경로 만들고
    • 각각 돌려서 남은게 min인 경로 구하면될듯

솔루션 코드 - 내가 푼

  • 10분컷
  • permutations
from itertools import permutations
import copy
def solution(k, dungeons):
    answer = -1
    #print(help(copy))
        
    for per in permutations(dungeons,len(dungeons)):
        my = copy.deepcopy(k)
        path = 0
        for p in per:
            # 입장 가능한지 체크
            if my >= p[0]:
                # 입장 후 피로도 소모
                my -= p[1]
                # 현재 path에서 참가한 던전 수
                path += 1
        answer = max(answer, path)
    
    return answer


솔루션 코드 - 블로그

  • dfs 풀이
    • 생각은 했는데 위에 방식이 더 쉬울 것 같아서 안해봤음
answer = 0
N = 0
visited = []


def dfs(k, cnt, dungeons):
    global answer
    if cnt > answer:
        answer = cnt

    for j in range(N):
        if k >= dungeons[j][0] and not visited[j]:
            visited[j] = 1                             # dfs하면서 중복된 길 안걷게 방문처리도
            dfs(k - dungeons[j][1], cnt + 1, dungeons) #<---- (중요) k에서 -- 해줘야함!!! (그리고 path++)
            visited[j] = 0


def solution(k, dungeons):
    global N, visited
    N = len(dungeons)
    visited = [0] * N
    dfs(k, 0, dungeons)
    return answer

profile
Do My Best

0개의 댓글