🥇 Problem Solving/Dynamic Programming

[Python] BOJ / 2156번 / 포도주 시식

2156번: 포도주 시식 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규 www.acmicpc.net 📝 문제 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규칙이 있다. 포도주 잔을 선택하면 그 잔에 들어있는 포도주는 모두 마셔야 하고, 마신 후에는 원래 위치에 다시 놓아야 한다. 연속으로 놓여 있는 3잔을 모두 마실 수는 없다. 효주는 될 수 있는 대로 많은 양의 포도주를 맛보기 위해서 어떤 포도주 잔을 선택해야 할지 고..

[Python] BOJ / 17070번 / 파이프 옮기기 1

17070번: 파이프 옮기기 1 유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의 www.acmicpc.net 📝 문제 유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의 번호이고, 행과 열의 번호는 1부터 시작한다. 각각의 칸은 빈 칸이거나 벽이다. 오늘은 집 수리를 위해서 파이프 하나를 옮기려고 한다. 파이프는 아래와 같은 형태이고, 2개의 연속된 칸을 차지하는 크기이다. 파이프는 회전시킬..

[Python] BOJ / 2225번 / 합분해

2225번: 합분해 첫째 줄에 답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 📝 문제 0부터 N까지의 정수 K개를 더해서 그 합이 N이 되는 경우의 수를 구하는 프로그램을 작성하시오. 덧셈의 순서가 바뀐 경우는 다른 경우로 센다(1+2와 2+1은 서로 다른 경우). 또한 한 개의 수를 여러 번 쓸 수도 있다. 📜 풀이 0부터 N까지의 정수 K개를 더해서 그 합이 N이 되는 경우의 수는 아래와 같은 규칙으로 구할 수 있을 것이다. dp[k][n]을 정수 k개를 더해서 그 합이 n이 되는 경우의 수라고 할 때 dp[k][n] = dp[k - 1][0] + dp[k - 1][1] + dp[k - 1][2] + ... + dp[k - 1][n - 1] + dp[k - 1..

[Python] BOJ / 2133번 / 타일 채우기

2133번: 타일 채우기 3×N 크기의 벽을 2×1, 1×2 크기의 타일로 채우는 경우의 수를 구해보자. www.acmicpc.net 📝 문제 3×N 크기의 벽을 2×1, 1×2 크기의 타일로 채우는 경우의 수를 구해보자. 📜 풀이 기본적으로 n이 홀수인 경우는 타일을 모두 채울 수 없음 n = 2부터 시작하여 벽의 크기가 2씩 증가할 때마다 새로운 모양으로 벽을 채우는 경우가 2씩 늘어남 따라서 다음과 같은 규칙이 성립됨 n = 2일 때의 경우의 수는 3가지 n = 4일 때의 경우의 수는 (n = 2일 때의 경우의 수) x (n = 2일 때의 경우의 수) + 2 n = 6일 때의 경우의 수는 (n = 2일 때의 경우의 수) x (n = 4일 때의 경우의 수) + 2 n = 8일 때의 경우의 수는 (n ..