본문 바로가기

dp43

[동적계획법/DP] 백준 9658 돌 게임 4 - 파이썬(Python) [ Contents ] 1. 문제 (링크 참조) 9658번: 돌 게임 4 상근이가 게임을 이기면 SK를, 창영이가 게임을 이기면 CY을 출력한다. www.acmicpc.net 2. 문제 풀이 어쩌다 보니 돌 게임 시리즈... 켠왕을 하고 있네요.. 2023.07.03 - [Algorithm] - [동적계획법/DP] 백준 9657 돌게임 3 - 파이썬(Python) [동적계획법/DP] 백준 9657 돌게임 3 - 파이썬(Python) [ Contents ] 1. 문제 (링크 참조) 9657번: 돌 게임 3 상근이가 게임을 이기면 SK를, 창영이가 게임을 이기면 CY을 출력한다. www.acmicpc.net 2. 문제 풀이 각 플레이어는 번갈아가며 돌을 1개, 3개 또는 4개를 star7sss.tistory.. 2023. 7. 3.
[동적계획법/DP] 백준 9657 돌게임 3 - 파이썬(Python) [ Contents ] 1. 문제 (링크 참조) 9657번: 돌 게임 3 상근이가 게임을 이기면 SK를, 창영이가 게임을 이기면 CY을 출력한다. www.acmicpc.net 2. 문제 풀이 각 플레이어는 번갈아가며 돌을 1개, 3개 또는 4개를 가져갈 수 있으며, 마지막 돌을 가져가는 사람이 게임을 이깁니다. n개가 주어졌을 때 이길 사람을 출력해야 합니다. (플레이어: 상근, 창영 / 시작은 상근이부터) 2023.07.03 - [Algorithm] - [동적계획법/DP] 백준 9656 돌 게임 2 - 파이썬(Python) [동적계획법/DP] 백준 9656 돌 게임 2 - 파이썬(Python) [ Contents ] 1. 문제 (링크 참조) 9656번: 돌 게임 2 상근이가 게임을 이기면 SK를, 창영.. 2023. 7. 3.
[동적계획법/DP] 백준 9656 돌 게임 2 - 파이썬(Python) [ Contents ] 1. 문제 (링크 참조) 9656번: 돌 게임 2 상근이가 게임을 이기면 SK를, 창영이가 게임을 이기면 CY을 출력한다. www.acmicpc.net 2. 문제 풀이 돌은 1개 혹은 3개씩 가져갈 수 있으며, 마지막 돌을 가져가는 사람이 지게 됩니다. 두 사람이 완벽하게 게임을 진행했다고 가정하고, n이 주어졌을 때 이기는 사람을 구해야 합니다. (상근이가 먼저 시작) 2022.02.12 - [Algorithm] - [Algorithm] 메모해두고 불러와서 사용하는 동적 프로그래밍(DP) [Algorithm] 메모해두고 불러와서 사용하는 동적 프로그래밍(DP) [ Contents ] 1. 동적 프로그래밍(Dynamic Programming, 동적계획법) 동적계획법(Dynamic .. 2023. 7. 3.
[DP/동적계획법] 백준 14916 거스름돈 - 파이썬(Python) [ Contents ] 1. 문제 (링크 참조) 14916번: 거스름돈 첫째 줄에 거스름돈 액수 n(1 ≤ n ≤ 100,000)이 주어진다. www.acmicpc.net 2. 문제 풀이 거스름돈을 2원과 5원 동전으로 거슬러주는 문제입니다. 이때 거슬러주는 동전의 개수는 최소가 되어야 합니다. 2022.01.31 - [Algorithm] - [그리디/Greedy] 백준 11047 동전 0 - Python [그리디/Greedy] 백준 11047 동전 0 - Python [ Contents ] 1. 문제 (링크 참조) 11047번: 동전 0 첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000) 둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 .. 2023. 7. 3.
[동적계획법/DP] 백준 1890 점프 - 파이썬(Python) [ Contents ] 1. 문제 (링크 참조) 1890번: 점프 첫째 줄에 게임 판의 크기 N (4 ≤ N ≤ 100)이 주어진다. 그 다음 N개 줄에는 각 칸에 적혀져 있는 수가 N개씩 주어진다. 칸에 적혀있는 수는 0보다 크거나 같고, 9보다 작거나 같은 정수이며, 가장 www.acmicpc.net 2. 문제 풀이 주어진 게임판의 적힌 숫자만큼 오른쪽 혹은 아래로 이동하여, 최우측 하단에 도착하는 경우의 수를 찾는 문제입니다. 3. 코드 from collections import deque import sys input = sys.stdin.readline # 입력 n = int(input()) board = [] for _ in range(n): board.append(list(map(int, i.. 2023. 7. 3.
[DP/동적계획법] 백준 1965 상자넣기 - 파이썬(Python) [ Contents ] 1. 문제 (링크 참조) 1965번: 상자넣기 정육면체 모양의 상자가 일렬로 늘어서 있다. 상자마다 크기가 주어져 있는데, 앞에 있는 상자의 크기가 뒤에 있는 상자의 크기보다 작으면, 앞에 있는 상자를 뒤에 있는 상자 안에 넣을 수가 www.acmicpc.net 2. 문제 풀이 상자의 크기가 나열된 수열이 주어집니다. 이전에 연속적으로 나왔던 작은 상자들은 이후에 나오는 큰 상자에 넣을 수 있습니다. 가장 많이 넣은 상자의 개수를 구해야 합니다. 2022.04.13 - [Algorithm] - [DP/동적계획법] 백준 11055 가장 큰 증가 부분 수열 - 파이썬(Python) [DP/동적계획법] 백준 11055 가장 큰 증가 부분 수열 - 파이썬(Python) [ Contents.. 2023. 7. 2.
[동적계획법/DP] 백준 9251 LCS - 파이썬(Python) [ Contents ] 1. 문제 (링크 참조) 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 2. 문제 풀이 ACAYKP CAPCAK 두 문자열의 LCS(Longest Common Subsequence, 최장 공통 부분 수열)을 구하는 문제입니다. 단순히 부분 문자열을 구하는 게 아니라, 떨어져 있어도 순서만 맞으면 공통 부분 수열이 될 수 있습니다. 2022.02.12 - [Algorithm] - [Algorithm] 메모해두고 불러와서 사용하는 동적 프로그래.. 2022. 9. 24.
[동적계획법/DP] 백준 1660 캡틴 이다솜 - 파이썬(Python) [ Contents ] 1. 문제 (링크 참조) 1660번: 캡틴 이다솜 캡틴 이다솜은 자신의 해적선에 적을 공격하기 위한 대포알을 많이 보관해 놓는다. 다솜이는 미적감각이 뛰어나기 때문에, 대포알은 반드시 사면체 모양으로 쌓아놓아야 한다고 생각한다. 사면 www.acmicpc.net 2. 문제 풀이 대포알을 반드시 사면체 모양으로 쌓아둘 때, 주어진 대포알로 만들 수 있는 최소의 '사면체'를 구하는 문제입니다. 2022.05.09 - [Algorithm] - [동적계획법/DP] 백준 12865 평범한 배낭 - 파이썬(Python) [동적계획법/DP] 백준 12865 평범한 배낭 - 파이썬(Python) [ Contents ] 1. 문제 (링크 참조) 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1.. 2022. 9. 3.
[DP/동적계획법] 백준 14495 피보나치 비스무리한 수열 - 파이썬(Python) [ Contents ] 1. 문제 (링크 참조) 14495번: 피보나치 비스무리한 수열 피보나치 비스무리한 수열은 f(n) = f(n-1) + f(n-3)인 수열이다. f(1) = f(2) = f(3) = 1이며 피보나치 비스무리한 수열을 나열하면 다음과 같다. 1, 1, 1, 2, 3, 4, 6, 9, 13, 19, ... 자연수 n을 입력받아 n번째 피보 www.acmicpc.net 2. 문제 풀이 f(n) = f(n-1) + f(n-3) 피보나치 수열 f(n) = f(n-1) + f(n-2)와 달리, f(n-3)이 들어간 수열입니다. 피보나치 수열과 마찬가지로, 점화식만 수정해서 DP로 구현합니다. 3. 코드 # 입력 n = int(input()) # DP cache = [1, 1, 1] for i.. 2022. 8. 31.

티스토리툴바