dp
-
[백준] 17485 진우의 달 여행 (Large) with PythonPS 2022. 6. 4. 01:03
📌 BOJ 17485 진우의 달 여행 (Large) 💡 조건 지구와 우주사이는 N X M 행렬로 나타낼 수 있으며 각 원소의 값은 우주선이 그 공간을 지날 때 소모되는 연료의 양이다. N, M (2 ≤ N, M ≤ 1000), 각 행렬의 원소값은 100 이하의 자연수이다. 지구 -> 달로 가는 경우 우주선이 움직일 수 있는 방향은 아래와 같다. 우주선은 전에 움직인 방향으로 움직일 수 없다. 즉, 같은 방향으로 두번 연속으로 움직일 수 없다. 진우의 목표는 연료를 최대한 아끼며 지구의 어느위치에서든 출발하여 달의 어느위치든 착륙하는 것이다. 최대한 돈을 아끼고 살아서 달에 도착하고 싶은 진우를 위해 달에 도달하기 위해 필요한 연료의 최소값을 계산하는 문제 다이나믹 프로그래밍, 완전탐색 유형의 문제 🖥 소..
-
[백준] 2631 줄세우기 with PythonPS 2022. 3. 18. 00:09
📌 BOJ 2631 줄세우기 💡 조건 선생님은 1번부터 N번까지 번호가 적혀있는 번호표를 아이들의 가슴에 붙여주었다. 선생님은 아이들을 효과적으로 보호하기 위해 목적지까지 번호순서대로 일렬로 서서 걸어가도록 하였다. 이동 도중에 보니 아이들의 번호순서가 바뀌어 다시 번호 순서대로 줄을 세우기 위해서 아이들의 위치를 옮기려고 한다. 아이들이 혼란스러워하지 않도록 하기 위해 위치를 옮기는 아이들의 수를 최소로 하려고 한다. 아이들의 수 N은 2 이상 200 이하의 정수이다. 다이나믹프로그래밍 유형의 문제 🖥 소스 코드 from sys import stdin n = int(stdin.readline()) num = [int(stdin.readline()) for _ in range(n)] dp = [0 for..
-
[백준] 4811 알약 with PythonPS 2022. 3. 9. 01:02
📌 BOJ 4811 알약 💡 조건 70세 박종수 할아버지는 매일 매일 약 반알을 먹는다. 손녀 선영이는 종수 할아버지에게 약이 N개 담긴 병을 선물로 주었다. 다음 날부터 종수는 병에서 약을 하나 꺼낸다. (약은 한 조각 전체 일 수도 있고, 쪼갠 반 조각 일 수도 있다) 반 조각이라면 그 약을 먹고, 아니라면 반을 쪼개서 한 조각을 먹고, 다른 조각은 다시 병에 넣는다. 종수는 손녀에게 한 조각을 꺼낸 날에는 W를, 반 조각을 꺼낸 날에는 H 보낸다. 손녀는 할아버지에게 받은 문자를 종이에 기록해 놓는다. 총 2N일이 지나면 길이가 2N인 문자열이 만들어지게 된다. 이때, 가능한 서로 다른 문자열의 개수는 총 몇 개일까? 입력은 최대 1000개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 ..
-
[백준] 1788 피보나치수의 확장 with PythonPS 2022. 3. 6. 21:35
📌 BOJ 1788 피보나치수의 확장 💡 조건 피보나치 수 F(n)을 n이 음수인 경우로도 확장시킬 수 있다. F(n) = F(n-1) + F(n-2)를 n ≤ 1일 때도 성립되도록 정의하는 것이다. n = 1일 때 F(1) = F(0) + F(-1)이 성립되어야 하므로, F(-1)은 1이 되어야 한다. n이 주어졌을 때, 피보나치 수 F(n)을 구하는 프로그램을 작성하는 프로그램. n은 음수로 주어질 수도 있다. n은 절댓값이 1,000,000을 넘지 않는 정수이다. 첫째 줄에 F(n)이 양수이면 1, 0이면 0, 음수이면 -1을 출력한다. 둘째 줄에는 F(n)의 절댓값을 출력한다. 이 수가 충분히 커질 수 있으므로, 절댓값을 1,000,000,000으로 나눈 나머지를 출력한다. 다이나믹프로그래밍 유형..
-
[백준] 1660 캡틴 이다솜 with PythonPS 2022. 3. 6. 01:17
📌 BOJ 1660 캡틴 이다솜 💡 조건 N은 300,000보다 작거나 같은 자연수이다. 사면체를 만드는 방법은 길이가 N인 정삼각형 모양을 만든다. 그 위에 길이가 N-1인 정삼각형 모양을 얹고 그위에 계속 해서 얹어서 1크기의 정삼각형 모양을 얹으면 된다. N개의 대포알로 만들 수 있는 사면체의 최소 개수를 출력하는 프로그램을 작성하는 문제 다이나믹프로그래밍 유형의 문제 🖥 소스 코드 from sys import stdin n = int(stdin.readline()) arr = [] num = 0 i = 1 while n > num: num += (i * (i + 1)) // 2 arr.append(num) i += 1 dp = [int(1e9) for i in range(n + 1)] for i ..
-
[백준] 11048 이동하기 with PythonPS 2022. 2. 19. 17:59
📌 BOJ 11048 이동하기 💡 조건 N×M 크기의 미로 (1 ≤ N, M ≤ 1,000) (r, c)에 있으면, (r+1, c), (r, c+1), (r+1, c+1)로 이동가능. 준규가 (N, M)으로 이동할 때, 가져올 수 있는 사탕 개수의 최댓값을 구하는 문제 N개 줄에는 총 M개의 숫자가 주어지며, r번째 줄의 c번째 수는 (r, c)에 놓여져 있는 사탕의 개수이다. 사탕의 개수는 0보다 크거나 같고, 100보다 작거나 같다. 다이나믹프로그래밍 유형의 문제 🖥 소스 코드 from sys import stdin n, m = map(int, stdin.readline().split()) arr = [] candy = [[0] * m for _ in range(n)] res = 0 for _ in ..
-
[백준] 1904 01타일 with PythonPS 2022. 2. 2. 00:43
📌 BOJ 1904 01타일 💡 조건 각각의 타일들은 0 또는 1이 쓰여 있는 낱장의 타일들이다. 동주가 지원이의 공부를 방해하기 위해 0이 쓰여진 낱장의 타일들을 붙여서 한 쌍으로 이루어진 00 타일들을 만들었다. 결국 현재 1 하나만으로 이루어진 타일 또는 0타일을 두 개 붙인 한 쌍의 00타일들만이 남게 되었다. N=1일 때 1만 만들 수 있고, N=2일 때는 00, 11을 만들 수 있다. (01, 10은 만들 수 없게 되었다.) 또한 N=4일 때는 0011, 0000, 1001, 1100, 1111 등 총 5개의 2진 수열을 만들 수 있다. N이 주어진다. (1 ≤ N ≤ 1,000,000) 지원이가 만들 수 있는 길이가 N인 모든 2진 수열의 개수를 15746으로 나눈 나머지를 출력한다. DP ..
-
[백준] 14916 거스름돈 with PythonPS 2022. 1. 26. 22:44
📌 BOJ 14916 거스름돈 💡 조건 동전의 개수가 최소가 되도록 거슬러 주어야 한다. 거스름돈 액수 n(1 ≤ n ≤ 100,000) DP, 수학 유형의 문제 🖥 소스 코드 from sys import stdin n = int(stdin.readline()) res = int(1e9) for i in range(n // 5, -1, -1): money = n - i * 5 cnt = i if money % 2 != 0: continue else: cnt += money // 2 res = min(cnt, res) print(res) if res != int(1e9) else print(-1)🔖 예제 및 실행결과 예제 13실행결과 5⌨️ 문제 풀이 5원 동전이 몇 개 일때 최소인지 구하면 된다. int..
-
[백준] 9461 파도반 수열 with PythonPS 2022. 1. 10. 18:54
📌 BOJ 9461 파도반 수열 💡 조건 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, N이 주어진다. (1 ≤ N ≤ 100) 파도반 수열 P(N)은 나선에 있는 정삼각형의 변의 길이. P(1)부터 P(10)까지 첫 10개 숫자는 1, 1, 1, 2, 2, 3, 4, 5, 7, 9 각 테스트 케이스마다 정수 N을 입력받아 P(N)을 출력. Dynamic Programming 알고리즘 유형의 문제 🖥 소스 코드 from sys import stdin dp = [0 for _ in range(101)] dp[0], dp[1], dp[2] = 1, 1, 1 for i in range(3, 101): dp[i] = dp[i - 3] + dp[i - 2] for _..
-