본문 바로가기

Algorithm/Dynamic Programming69

[파이썬] 백준 1949 : 우수마을 (골드2) [파이썬] 백준 1949 : 우수마을 (골드2) 1949번: 우수 마을 첫째 줄에 정수 N이 주어진다. (1 ≤ N ≤ 10,000) 둘째 줄에는 마을 주민 수를 나타내는 N개의 자연수가 빈칸을 사이에 두고 주어진다. 1번 마을부터 N번 마을까지 순서대로 주어지며, 주민 수는 10,00 www.acmicpc.net 문제 풀이 0. 방향성 생각 DFS를 사용해서 루트노드에서 시작해서 리프노드부터 DP 시작을 해준다. DFS를 마치고 나면 DP 루트노드를 확인하면 가중치 합이 저장되게 작성한다. 상태는 두 가지 상태가 존재한다. dp[state][노드수]로 dp 테이블 작성하기 1. 입력 import sys sys.setrecursionlimit(10**6) input = lambda : sys.stdin... 2023. 8. 14.
[파이썬] 백준 2342 : Dance Dance Revolution (골드3) [파이썬] 백준 2342 : Dance Dance Revolution (골드3) 문제 풀이 0. 방향성 생각 발 옮기기 전 위치 -> 옮긴 후 위치 비용을 정리하는 딕셔너리 cost 정의 25개 상태 왼발5가지*오른발5가지, 각 상태로 올 수 있는 경우 중 가장 작은 코스트 선택 입력으로 1 2 2 4 0이 들어오면 마지막 0은 제외하고 stage 0에서 4개의 단계를 거쳐 stage 4에 도달해야한다. 각 stage에 도달하는 모든 상태를 확인하면서 DP 업데이트. 1. 입력, DP 초기화 import sys input = lambda : sys.stdin.readline().rstrip() command = list(map(int,input().split())) stages = len(command).. 2023. 8. 8.
[파이썬] 백준 1563 : 개근상 (골드4) [파이썬] 백준 1563 : 개근상 (골드4) 1563번: 개근상 백준중학교에서는 학기가 끝날 무렵에 출결사항을 보고 개근상을 줄 것인지 말 것인지 결정한다. 이 학교는 이상해서 학생들이 학교를 너무 자주 빠지기 때문에, 개근상을 주는 조건이 조금 독 www.acmicpc.net 문제 풀이 0. 방향성 생각 상태도 DP로 접근 상태도 분류 누적지각0~1회,연속결석0~2회,개근상불가 -> 총 7가지 경우 1. 입력 n = int(input()) dp = [[0]*7 for _ in range(n)] dp[0] = [1,1,0,1,0,0,0] k = 1000000 filters = [[1,1,1,0,0,0,0], [1,0,0,0,0,0,0], [0,1,0,0,0,0,0], [1,1,1,1,1,1,0], [0.. 2023. 8. 6.
[파이썬] 프로그래머스 : 에어컨 (Lv.3) [파이썬] 프로그래머스 : 에어컨 (Lv.3) 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 0. 방향성 생각 1. 온도는 대칭적임. 상대적인 대소관계만 중요. 바깥 온도, t1이 0,5인 경우랑 바깥온도,t2가 20,25인 경우는 같다. 이후 인덱스 맞춰주기. 시작 온도를 0부터 매핑 2. 이전에 사용했던 전력량과 현재 상태 이용해서 전력량 계산 -> DP 1. 온도 매핑, DP 만들기 def solution(Tout,T1,T2,a,b,info): if Tout < T1 : Tout = T2 + (T1-Tout) T1,T2,Tout = 0,T2-T.. 2023. 8. 4.

티스토리툴바