다이나믹프로그래밍
-
[백준] 9658 돌 게임 4 with PythonPS 2023. 4. 7. 15:07
📌 BOJ 9658 돌 게임 4 💡 조건 탁자 위에 돌 N개가 있다. 상근이와 창영이는 턴을 번갈아가면서 돌을 가져가며, 돌은 1개, 3개 또는 4개 가져갈 수 있다. 마지막 돌을 가져가는 사람이 게임을 지게 된다. 두 사람이 완벽하게 게임을 했을 때, 이기는 사람을 구하는 문제. 게임은 상근이가 먼저 시작한다. 첫째 줄에 N이 주어진다. (1 ≤ N ≤ 1000) 상근이가 게임을 이기면 SK를, 창영이가 게임을 이기면 CY을 출력한다. 다이나믹 프로그래밍 유형의 문제 🔖 예제 및 실행결과 예제 1 6 실행결과 1 SK ⌨️ 문제 풀이 돌 게임 3 와의 상황을 반대로 계산하면 된다. 🖥 소스 코드 from sys import stdin n = int(stdin.readline()) dp = [0, 0, ..
-
[백준] 9657 돌 게임 3 with PythonPS 2023. 4. 4. 17:46
📌 BOJ 9657 돌 게임 3 💡 조건 탁자 위에 돌 N개가 있다. 상근이와 창영이는 턴을 번갈아가면서 돌을 가져가며, 돌은 1개, 3개 또는 4개 가져갈 수 있다. 마지막 돌을 가져가는 사람이 게임을 이기게 된다. 두 사람이 완벽하게 게임을 했을 때, 이기는 사람을 구하는 문제. 게임은 상근이가 먼저 시작한다. 첫째 줄에 N이 주어진다. (1 ≤ N ≤ 1000) 상근이가 게임을 이기면 SK를, 창영이가 게임을 이기면 CY을 출력한다. 다이나믹 프로그래밍 유형의 문제 🔖 예제 및 실행결과 예제 1 6실행결과 1 SK⌨️ 문제 풀이 상근이를 기준으로 DP 배열을 구성할 것이다. 그렇다면, 어떻게하면 상근이가 이길 수 있을지에 대해서 생각해보면 좋다. "완벽하게 게임을 한다" 라는 구절을 통해서 어떻게든..
-
[백준] 9656 돌 게임2 with PythonPS 2023. 4. 4. 17:31
📌 BOJ 9656 돌 게임2 💡 조건 탁자 위에 돌 N개가 있다. 상근이와 창영이는 턴을 번갈아가면서 돌을 가져가며, 돌은 1개 또는 3개 가져갈 수 있다. 마지막 돌을 가져가는 사람이 게임을 지게 된다. 두 사람이 완벽하게 게임을 했을 때, 이기는 사람을 구하는 문제. 게임은 상근이가 먼저 시작한다. 첫째 줄에 N이 주어진다. (1 ≤ N ≤ 1000) 상근이가 게임을 이기면 SK를, 창영이가 게임을 이기면 CY을 출력한다. 다이나믹 프로그래밍 유형의 문제 🔖 예제 및 실행결과 예제 1 4 실행결과 1 SK ⌨️ 문제 풀이 BOJ 9655 돌 게임 의 문제 풀이와 매우 비슷하다. 9655 돌 게임 문제 풀이 를 참고하여 아이디어를 얻어보자. 🖥 소스 코드 from sys import stdin pri..
-
[백준] 9655 돌 게임 with PythonPS 2023. 4. 4. 17:19
📌 BOJ 9655 돌 게임 💡 조건 탁자 위에 돌 N개가 있다. 상근이와 창영이는 턴을 번갈아가면서 돌을 가져가며, 돌은 1개 또는 3개 가져갈 수 있다. 마지막 돌을 가져가는 사람이 게임을 이기게 된다. 두 사람이 완벽하게 게임을 했을 때, 이기는 사람을 구하는 문제. 게임은 상근이가 먼저 시작한다. 첫째 줄에 N이 주어진다. (1 ≤ N ≤ 1000) 상근이가 게임을 이기면 SK를, 창영이가 게임을 이기면 CY을 출력한다. 다이나믹 프로그래밍 유형의 문제 🔖 예제 및 실행결과 예제 1 5 실행결과 1 SK ⌨️ 문제 풀이 상근이를 기준으로 DP 배열을 구성할 것이다. 그렇다면, 어떻게하면 상근이가 이길 수 있을지에 대해서 생각해보면 좋다. "완벽하게 게임을 한다" 라는 구절을 통해서 어떻게든 상근이..
-
[백준] 14495 피보나치 비스무리한 수열 with PythonPS 2022. 7. 17. 01:39
📌 BOJ 14495 피보나치 비스무리한 수열 💡 조건 피보나치 비스무리한 수열은 f(n) = f(n-1) + f(n-3)인 수열이다. f(1) = f(2) = f(3) = 1이며 피보나치 비스무리한 수열을 나열하면 다음과 같다. 자연수 n을 입력받아 n번째 피보나치 비스무리한 수열을 구하는 문제. 자연수 n의 범위는 (1 ≤ n ≤ 116) 이다. DP 유형의 문제 🖥 소스 코드 from sys import stdin dp = [0 for _ in range(120)] dp[0:3] = [1, 1, 1, 2] for x in range(4, 117): dp[x] = (dp[x - 3] + dp[x - 1]) print(dp[int(stdin.readline()) - 1])🔖 예제 및 실행결과 예제 10..
-
[백준] 14494 다이나믹이 뭐예요? with PythonPS 2022. 7. 14. 23:07
📌 BOJ 14494 다이나믹이 뭐예요? 💡 조건 다이나믹 프로그래밍(동적 계획법), 다이나믹은 이름이 엄청 거창하지만 사실 이름에 비해 개념은 간단하다. 다이나믹의 기본 아이디어는 바로 이전에 계산한 값을 사용해서 (= 이미 계산된 값을 사용해서, 어려운 말로 메모이제이션.) 반복되는 똑같은 연산 횟수를 줄이는 것. 다차원 배열로도 가능하다. 오른쪽, 아래쪽으로만 움직일 수 있을 때, D[1][1]에서 D[x][y]까지 도달하는 경우의 수를 구하는 문제는 일일히 모든 경우를 다 계산할 필요 없이, D[i][j] = (i, j)에 도달하는 누적 경우의 수 = D[i-1][j] + D[i][j-1]를 세워서 해결할 수도 있다. →, ↓, ↘의 세 방향만 사용해서 한 번에 한 칸씩 이동할 때, 왼쪽 위 (1..
-
[백준] 1520 내리막 길 with PythonPS 2022. 6. 10. 15:44
📌 BOJ 1520 내리막 길 💡 조건 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 한 칸은 한 지점을 나타내는데 각 칸에는 그 지점의 높이가 쓰여 있으며, 각 지점 사이의 이동은 지도에서 상하좌우 이웃한 곳끼리만 가능하다. 현재 제일 왼쪽 위 칸이 나타내는 지점에 있는 세준이는 제일 오른쪽 아래 칸이 나타내는 지점으로 가려고 한다. 그런데 가능한 힘을 적게 들이고 싶어 항상 높이가 더 낮은 지점으로만 이동하여 목표 지점까지 가고자 한다. 위와 같은 지도에서는 다음과 같은 세 가지 경로가 가능하다. 지도가 주어질 때 이와 같이 제일 왼쪽 위 지점에서 출발하여 제일 오른쪽 아래 지점까지 항상 내리막길로만 이동하는 경로의 개수를 구하는 프로그램을 작성하시오. 첫째 줄에는 지도의 세..
-
[백준] 1309 동물원 with PythonPS 2022. 6. 7. 20:22
📌 BOJ 1309 동물원 💡 조건 어떤 동물원에 가로로 두칸 세로로 N칸인 아래와 같은 우리가 있다. 이 동물원에는 사자들이 살고 있는데 사자들을 우리에 가둘 때, 가로로도 세로로도 붙어 있게 배치할 수는 없다. 동물원 조련사의 머리가 아프지 않도록 우리가 2*N 배열에 사자를 배치하는 경우의 수가 몇 가지인지를 알아내는 프로그램을 작성하는 문제. 사자를 한 마리도 배치하지 않는 경우도 하나의 경우의 수로 친다고 가정한다. 첫째 줄에 우리의 크기 N(1≤N≤100,000)이 주어진다. 첫째 줄에 사자를 배치하는 경우의 수를 9901로 나눈 나머지를 출력하자. DP, 다이나믹 프로그래밍 유형의 문제 🖥 소스 코드 from sys import stdin n = int(stdin.readline()) dp ..
-
[백준] 2342 Dance Dance Revolution with PythonPS 2022. 5. 20. 20:50
📌 BOJ 2342 Dance Dance Revolution 💡 조건 편의상 중점을 0, 위를 1, 왼쪽을 2, 아래를 3, 오른쪽을 4라고 정하자. 처음에 게이머는 두 발을 중앙에 모으고 있다.(그림에서 0의 위치) 그리고 게임이 시작하면, 지시에 따라 왼쪽 또는 오른쪽 발을 움직인다. 하지만 그의 두 발이 동시에 움직이지는 않는다. 두 발이 같은 지점에 있는 것이 허락되지 않는다. 한 발이 1의 위치에 있고, 다른 한 발이 3의 위치에 있을 때, 3을 연속으로 눌러야 한다면, 3의 위치에 있는 발로 반복해야 눌러야 한다. 발을 이동할 때 힘을 사용하게 된다. 중앙에 있던 발이 다른 지점으로 움직일 때, 2의 힘을 사용하게 된다. 다른 지점에서 인접한 지점으로 움직일 때는 3의 힘을 사용하게 된다. 반..
-
[백준] 2302 극장 좌석 with PythonPS 2022. 3. 31. 04:31
📌 BOJ 2302 극장 좌석 💡 조건 어떤 극장의 좌석은 한 줄로 되어 있으며 왼쪽부터 차례대로 1번부터 N번까지 번호가 매겨져 있다. 공연을 보러 온 사람들은 자기의 입장권에 표시되어 있는 좌석에 앉아야 한다. 자기의 바로 왼쪽 좌석 또는 바로 오른쪽 좌석으로는 자리를 옮길 수 있다. 이 극장에는 “VIP 회원”들이 있다. 이 사람들은 반드시 자기 좌석에만 앉아야 하며 옆 좌석으로 자리를 옮길 수 없다. 오늘 공연은 입장권이 매진되어 1번 좌석부터 N번 좌석까지 모든 좌석이 다 팔렸다. VIP 회원들의 좌석 번호들이 주어졌을 때, 사람들이 좌석에 앉는 서로 다른 방법의 가짓수를 구하는 프로그램을 작성하시오. N은 1 이상 40 이하이다. 둘째 줄에는 고정석의 개수 M이 입력된다. 방법의 가짓수는 2,..