Algorithm/Dynamic Programming69 [파이썬] 백준 17404 : RGB거리 2 (골드4) [파이썬] 백준 17404 : RGB거리 2 (골드4) 17404번: RGB거리 2 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 문제 풀이 0. 방향성 생각 각 색깔별로 시작해서 마지막에는 자신과 다른 색으로 끝난 색의 값 2개씩 받는다. 총 6개 중 최소값을 출력. 1. 입력 import sys input = lambda : sys.stdin.readline().rstrip() n = int(input()) arr = [] for _ in range(n): arr.append(list(map(int,inp.. 2023. 7. 22. [파이썬] 백준 1149 : RGB거리 (실버1) [파이썬] 백준 1149 : RGB거리 (실버1) 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 문제 풀이 방향성 생각 2차원 DP를 만들어서 현재 밟는 지점에 누적 비용이 얼마인지 업데이트 한다. DP의 가로는 0 1 2, R G B를 배정한다. n은 칠해야하는 집의 수. 출발점으로부터 거리라고 생각한다. 초기값은 arr의 첫부분과 동일하게 지정. 다음 DP의 R = 다음 arr R + min(G현재,B현재) 이런식으로 현재 밟은 색깔이 아닌 곳 2개의 비용의 중 최소값을 더해준다. .. 2023. 7. 20. [파이썬] 백준 1562: 계단 수 (골드1) [파이썬] 백준 1562: 계단 수 (골드1) 1562번: 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 문제 풀이 0. 방향성 생각 생각을 조금 다르게 해서 접근. 3차원 DP 리스트 만들어서 풀이 비유를 하자면 달리기 0층에서 달리는 선수가 3층 끝에 도달하는 경우의 수를 카운트. 0번 레인, 9번 레인에는 엘베가 있다고 생각하면 된다. 한 번이라도 접근했으면 다음 층으로 이동. 리스트를 4 * 10 * n 형태로 만든다. 4는 층의 개수. (0~3층) / 10은 사용 가능한 lane 수 / n은 달려야할 거리. 0층은 아직 0번레인 9번레인을 선택하지 않은 사람 1층은 0번 레인을 선택해서 다음 층으로 올라간 사람 2층은 9번 레인을 선.. 2023. 7. 18. [파이썬] 프로그래머스 : 땅따먹기 (Lv.2) [파이썬] 프로그래머스 : 땅따먹기 (Lv.2) 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 방향성 생각 딱봐도 DP문제긴 한데 평소같으면 BFS DFS로 풀겠는데 DP 실력이 안늘어서 DP 연습.. 출발점 4개에 대해서 전부 DP 돌려서 저장해주면 된다. 점화식이라고 하기엔 이전값 + 이전 인덱스 아닌거 중 최대라서 크게 어렵지는 않다. def solution(land): dp = [[0]*4 for _ in range(len(land))] dp[0] = land[0] for i in range(1,len(land)): for j in range.. 2023. 7. 8. 이전 1 ··· 13 14 15 16 17 18 다음
