본문 바로가기

Algorithm/Dynamic Programming69

[파이썬] 프로그래머스 : 산 모양 타일링 (레벨3) [파이썬] 프로그래머스 : 산 모양 타일링 (레벨3)https://school.programmers.co.kr/learn/courses/30/lessons/258705풀이방향성 생각유명한 타일링 DP. 개꿀문제각 지점에 대해서 가능한 경우의 수를 DP로 채운다.점화식을 찾아서 바텀업으로 풀이.탑다운으로 풀기에는 바로 분할해서 보기 쉽지 않다.이전 타일 상태에서 경로만 지정해주면 바텀업이 쉽다.$N=4$, $tops=[1,1,0,1]$의 경우에는 DP 테이블을 다음과 같이 나타낼 수 있다.0 1 0 1 0 0 0 1 01 1 1 1 1 1 1 1 11은 타일이 깔린 부분, 0은 타일이 없는 부분초기 상태 DP를 채워보면0 3 ? ? ? ? ? ? ?1 2 * ? ? ? ? ? ?CASE1) 2 옆의 아래쪽.. 2024. 6. 12.
[파이썬] 백준 12869 : 뮤탈리스크 (골드4) [파이썬] 백준 12869 : 뮤탈리스크 (골드4)https://www.acmicpc.net/problem/12869풀이방향성 생각바텀업보다는 탑다운이 짜기 더 쉬워보인다.전체코드import syssys.setrecursionlimit(10**6)N = int(input())HP = list(map(int,input().split()))for _ in range(3-N): HP.append(0)dp = {}def dfs(a,b,c): # 재방문 if (a,b,c) in dp: return dp[(a,b,c)] # 탈출조건 if (a,b,c) == (0,0,0): return 0 answer = min(dfs(max(a-9,0),max(b-3,0),.. 2024. 6. 8.
[파이썬] 프로그래머스 : 숫자 타자 대회 (레벨3) [파이썬] 프로그래머스 : 숫자타자대회 (레벨3)https://school.programmers.co.kr/learn/courses/30/lessons/136797풀이방향성 생각백준의 DDR과 비슷한 문제.키패드가 12개에 왼손 오른손 처리하면 144개라 양이 좀 많다.다익스트라로 좌표 이동 시 걸리는 가중치맵을 구한다.DP 테이블을 순회하면서 최대값 갱신해주기.전체코드import heapq as hqfrom collections import defaultdict as dddef solution(numbers): # 키패드 arr = [['1','2','3'], ['4','5','6'], ['7','8','9'], ['*','0','#']].. 2024. 5. 9.
[파이썬] 프로그래머스 : 올바른 괄호의 개수 [파이썬] 프로그래머스 : 올바른 괄호의 개수 (레벨4) https://school.programmers.co.kr/learn/courses/30/lessons/12929 풀이 방향성 생각 DFS로 탐색하면서 중복 방문한 노드는 메모제이션한 값으로 프루닝. 전체코드 def solution(n): dp = [[-1]*(n+1) for _ in range(n+1)] def dfs(l,r): # 맞춰서 도달 했으면 카운팅 if (l,r) == (0,0): return 1 # r을 더 많이쓰면 올바르지 않음. 괄호는 주어진 개수만 사용해야함 if l>r or l 2024. 4. 23.

티스토리툴바