반응형 Problem Solving/Dynamic Programming20 [다이나믹 프로그래밍 / 파이썬 ] 백준 1947번 : 선물 전달 / 골드 2 https://www.acmicpc.net/problem/1947 1947번: 선물 전달 경우의 수를 1,000,000,000으로 나눈 나머지를 첫째 줄에 출력한다. www.acmicpc.net n = int(input()) temp = [0, 1, 2] if n < 3: print(temp[n-1]) quit() dp = [0 for _ in range(n+1)] dp[1] = 0 dp[2] = 1 dp[3] = 2 for i in range(4, n+1): dp[i] = ((dp[i-1] + dp[i-2])*(i-1)) % 1000000000 print(dp[n]) 각자 가져온 선물을 나눠 갖는데, 본인 것은 가지면 안된다. 이때 경우의 수는? 매우 간단한 질문이지만 규칙을 찾는 것은 상당히 어렵다... 2022. 3. 5. [다이나믹 프로그래밍] 백준 11054번: 가장 긴 바이토닉 부분 수열 / 골드 3 https://www.acmicpc.net/problem/11054 11054번: 가장 긴 바이토닉 부분 수열 첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000) www.acmicpc.net well-known problem인 LIS를 조금 응용하면 풀 수 있는 문제! n = int(input()) nums = list(map(int, input().split())) dp_asc = [0 for _ in range(n)] dp_desc = [0 for _ in range(n)] for i in range(n): max_val = 0 for j in range(i): if nums[j] < nums[i]:.. 2021. 12. 3. [다이나믹 프로그래밍] 백준 9465번: 스티커 / 실버 1 https://www.acmicpc.net/problem/9465 9465번: 스티커 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 두 줄에는 n개의 정수가 주어지며, 각 정수는 그 위치에 해당하는 스티커의 www.acmicpc.net probs = int(input()) for _ in range(probs): n = int(input()) up = list(map(int, input().split())) down = list(map(int, input().split())) dp1 = [0 for _ in range(n)] dp2 = [0 for _ in range(n)] dp1[0]= up[0] dp2[0]= do.. 2021. 11. 15. [다이나믹 프로그래밍] 백준 2579번: 계단 오르기 / 실버 3 https://www.acmicpc.net/problem/2579 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net 잘 알려진 계단 오르기 문제와 유사하지만, 까다로운 조건 하나가 추가 되었다. 바로 연속한 세 계단을 오를 수는 없다는 것이다. 이걸 어떻게 dp에 적용할 수 있을지 고민하는 것 때문에 실버3인데도 꽤 어려움을 느꼈다. 어떤 x번째 계단에 도착하는 상황을 가정해보자. 이전 스텝에서는 x-1번째 또는 x-2번째 계단에 있었을 것이다. 그럼 그 전 스텝에서는? 이렇게 전전 스텝까지 생각해봤을 때, x번째 계단을 .. 2021. 9. 15. [다이나믹 프로그래밍] 백준 17069번: 파이프 옮기기 2 / 골드 5 https://www.acmicpc.net/problem/17069 17069번: 파이프 옮기기 2 유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의 www.acmicpc.net dp 문제임을 깨달으면 접근할만 한데 어려운 이유는 dp임을 깨닫기가 쉽지 않다. 첫 시도를 bfs로 했었고 마지막 예제에서 시간 초과가 발생했다. 풀이 방법은, dp는 3차원 리스트로 만든다. n*n*3이다. 마지막이 3인 이유는 각 horizontal, vertical, diagonal 방향의 정보를 담고 있어야 하기 때문. 처음엔 모든 성분을 0으로 초기화해준다. 그.. 2021. 9. 5. [다이나믹 프로그래밍] 백준 12865번: 평범한 배낭 / 골드 5 https://www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net 유명한 배낭 문제!! n, k = map(int, input().split()) items = [] for i in range(n): w, v = map(int, input().split()) items.append([w, v]) dp = [[0]*(k+1) for _ in range(n+1)] for i in range(1, n+.. 2021. 9. 4. 이전 1 2 3 4 다음 반응형
