dp
-
[백준] 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 배열을 구성할 것이다. 그렇다면, 어떻게하면 상근이가 이길 수 있을지에 대해서 생각해보면 좋다. "완벽하게 게임을 한다" 라는 구절을 통해서 어떻게든 상근이..
-
[백준] 1890 점프 with PythonPS 2022. 8. 9. 17:33
📌 BOJ 1890 점프 💡 조건 N×N 게임판에 수가 적혀져 있다. N (4 ≤ N ≤ 100) 이 게임의 목표는 가장 왼쪽 위 칸에서 가장 오른쪽 아래 칸으로 규칙에 맞게 점프를 해서 가는 것이다. 각 칸에 적혀있는 수는 현재 칸에서 갈 수 있는 거리를 의미한다. 칸에 적혀있는 수는 0보다 크거나 같고, 9보다 작거나 같은 정수이며, 가장 오른쪽 아래 칸에는 항상 0이 주어진다. 반드시 오른쪽이나 아래쪽으로만 이동해야 한다. 0은 더 이상 진행을 막는 종착점이며, 항상 현재 칸에 적혀있는 수만큼 오른쪽이나 아래로 가야 한다. 한 번 점프를 할 때, 방향을 바꾸면 안 된다. 즉, 한 칸에서 오른쪽으로 점프를 하거나, 아래로 점프를 하는 두 경우만 존재한다. 가장 왼쪽 위 칸에서 가장 오른쪽 아래 칸으로..
-
[백준] 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..
-
[백준] 2225 합분해 with PythonPS 2022. 6. 17. 12:25
📌 BOJ 2225 합분해 💡 조건 덧셈의 순서가 바뀐 경우는 다른 경우로 센다(1+2와 2+1은 서로 다른 경우). 또한 한 개의 수를 여러 번 쓸 수도 있다. 첫째 줄에 두 정수 N(1 ≤ N ≤ 200), K(1 ≤ K ≤ 200)가 주어진다. 첫째 줄에 답을 1,000,000,000으로 나눈 나머지를 출력한다. 0부터 N까지의 정수 K개를 더해서 그 합이 N이 되는 경우의 수를 구하는 문제 DP, 다이나믹프로그래밍 유형의 문제 🖥 소스 코드 n, k = map(int, input().split()) mod = 1000000000 dp = [[0] * (n + 1) for _ in range(k + 1)] dp[0][0] = 1 for i in range(1, k + 1): for j in rang..
-
[백준] 1915 가장 큰 정사각형 with PythonPS 2022. 6. 17. 11:50
📌 BOJ 1915 가장 큰 정사각형 💡 조건 아래와 같은 예제에서는 가운데의 2×2 배열이 가장 큰 정사각형이다. 첫째 줄에 n, m(1 ≤ n, m ≤ 1,000)이 주어진다. 다음 n개의 줄에는 m개의 숫자로 배열이 주어진다. n×m의 0, 1로 된 배열이 있다. 이 배열에서 1로 된 가장 큰 정사각형의 크기를 구하는 문제. DP, 다이나믹프로그래밍 유형의 문제 🖥 소스 코드 from sys import stdin """ """ n, m = map(int, stdin.readline().split()) arr = [] for _ in range(n): arr.append(list(map(int, list(stdin.readline().rstrip())))) ans = 0 dp = [[0] * (m ..
-
[백준] 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 ..