다이나믹프로그래밍
-
[백준] 12761 돌다리 with PythonPS 2022. 3. 23. 16:33
📌 BOJ 12761 돌다리 💡 조건 돌의 번호는 0 부터 100,000 까지 존재하고 동규는 N번 돌 위에, 주미는 M번 돌 위에 위치하고 있다. 동규는 주미가 너무 보고싶기 때문에 최대한 빨리 주미에게 가기 위해 A, B 만큼의 힘을 가진 스카이 콩콩을 가져왔다. 현 위치에서 +1칸, -1칸을 이동할 수 있고, 스카이 콩콩을 이용해 현 위치에서 A나 B만큼 좌우로 점프할 수 있으며, 순간적으로 힘을 모아 현 위치의 A배 나 B배의 위치로 이동을 할 수 있다. 이동 과정에서 100,000보다 크거나 0보다 작은 번호의 돌은 존재하지 않으므로 갈 수 없고, 같은 방법을 계속 사용해도 되며 항상 도달할 수 있는 케이스만 주어진다. 첫 줄에 스카이 콩콩의 힘 A와 B, 그리고 동규의 현재위치 N, 주미의 현..
-
[백준] 2096 내려가기 with PythonPS 2022. 3. 12. 02:29
📌 BOJ 2096 내려가기 💡 조건 N줄에 0 이상 9 이하의 숫자가 세 개씩 적혀 있다. 내려가기 게임을 하고 있는데, 이 게임은 첫 줄에서 시작해서 마지막 줄에서 끝나게 되는 놀이이다. 먼저 처음에 적혀 있는 세 개의 숫자 중에서 하나를 골라서 시작하게 된다. 그리고 다음 줄로 내려가는데, 다음 줄로 내려갈 때에는 다음과 같은 제약 조건이 있다. 바로 아래의 수로 넘어가거나, 아니면 바로 아래의 수와 붙어 있는 수로만 이동할 수 있다는 것이다. 최대 점수, 최소 점수를 구하는 프로그램을 작성하는 문제 첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 숫자가 세 개씩 주어진다. 숫자는 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 중의 하나가 된다. 첫째 줄에 얻을 수..
-
[백준] 8394 악수 with PythonPS 2022. 3. 2. 23:53
📌 BOJ 8394 악수 💡 조건 회의가 끝났고, 이제 악수를 하는 시간이다. 모든 사람은 직사각형 탁자 하나의 한 면에 앉아있다. 자리를 벗어나지 않고 악수를 하는 방법의 수를 구하는 문제 각 사람들은 자신의 왼쪽이나 오른쪽에 있는 사람들과 악수를 할 수 있다. (안 할 수도 있다) 첫째 줄에 회의에 참석한 사람의 수 n (1 ≤ n ≤ 10,000,000)이 주어진다. 수가 매우 커질 수 있기 때문에, 마지막 자리만 출력한다. 다이나믹프로그래밍 유형의 문제 🖥 소스 코드 from sys import stdin n = int(stdin.readline()) arr = [0 for _ in range(n + 1)] arr[0], arr[1] = 1, 1 for i in range(2, n + 1): ar..
-
[백준] 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 ..
-
[백준] 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 _..
-