목록백준/DP (47)
Study hard
www.acmicpc.net/problem/11060 11060번: 점프 점프 재환이가 1×N 크기의 미로에 갇혀있다. 미로는 1×1 크기의 칸으로 이루어져 있고, 각 칸에는 정수가 하나 쓰여 있다. i번째 칸에 쓰여 있는 수를 Ai라고 했을 때, 재환이는 Ai이하만큼 오른쪽으로 � www.acmicpc.net [풀이] DP로 풀 수 있는 문제! DP[i] : i번째 칸에서 최소 몇 번 점프해야 N번째 칸에 갈 수 있는지 주어진 칸이 한 칸일 경우, 한 번만 점프해서 N번째 칸에 갈 수 있는 경우, 점프할 수 없는 칸인 경우를 모두 신경써줘야 한다. #include #include //memset using namespace std; int N; int Maze[1001]; int DP[1001]; vo..
www.acmicpc.net/problem/11048 11048번: 이동하기 준규는 N×M 크기의 미로에 갇혀있다. 미로는 1×1크기의 방으로 나누어져 있고, 각 방에는 사탕이 놓여져 있다. 미로의 가장 왼쪽 윗 방은 (1, 1)이고, 가장 오른쪽 아랫 방은 (N, M)이다. 준규는 �� www.acmicpc.net [풀이] 진행할수록 범위가 좁아지므로 DP를 사용한다. 어느 방향에서 와야 값이 커지는 지 확인 점화식 DP[i][j] = Maze[i][j] + max(DP[i-1][j], max(DP[i][j-1], DP[i-1][j-1])) #include #include //max using namespace std; int N, M; int Maze[1001][1001]; int DP[1001][1..
https://www.acmicpc.net/problem/11052 11052번: 카드 구매하기 첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 1,000) 둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1 ≤ Pi ≤ 10,000) www.acmicpc.net ※점화식※ dp[i] : i개 카드 구매 위해 민규가 지불해야 하는 금액의 최댓값 dp[1] = P[1] dp[x] = max(P[x], (dp[x-j][j]중 최댓값)) (1≤j≤x/2) #include #include using namespace std; int N; long long P[1001]; long long dp[1001]; void DP() { dp[1] = P[1]; for (int i..
https://www.acmicpc.net/problem/2011 2011번: 암호코드 문제 상근이와 선영이가 다른 사람들이 남매간의 대화를 듣는 것을 방지하기 위해서 대화를 서로 암호화 하기로 했다. 그래서 다음과 같은 대화를 했다. 상근: 그냥 간단히 암호화 하자. A를 1이� www.acmicpc.net 입력에 뛰어쓰기가 없고, 몇 자리수인지도 알려주지 않기 때문에 먼저 string으로 암호를 입력 받은 뒤에 int형 배열에 형변환 시켜 저장하는 방법을 썼다. ※점화식※ dp[i] : i번째 숫자까지 봤을 때 읽을 수 있는 단어의 개수 두 가지 경우가 있다. 1. i번째 숫자를 한자리 수로 따로 읽는 경우: dp[i] = dp[i-1]+dp[i] (조건:Code_Num[i]가 0이 아닌 한자리 자연..
https://www.acmicpc.net/problem/2225 2225번: 합분해 첫째 줄에 답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net ※점화식※ dp[i][j] : 0부터 j까지의 정수 i개를 더해서 그 합이 j가 되는 경우의 수 dp[1][0~N] = 1로 초기화 (자기자신밖에 안 되기 때문) ex) K=2, N=2 0부터 2까지 정수 2개 더해서 그 합이 2가 되는 경우 : 0+2, 1+1, 2+0 3개 0 + 2 : 1개 더해서 0 나오는 경우 + K번째에 2 1 + 1 : 1개 더해서 1 나오는 경우 + K번째에 1 2 + 0 : 1개 더해서 2 나오는 경우 + K번째에 0 dp[K][N] = dp[K-1][0] + ··· + dp[K-1][N] ..
https://www.acmicpc.net/problem/9461 9461번: 파도반 수열 문제 오른쪽 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 � www.acmicpc.net ※점화식※ x = 0~4까지 초기화 해준다. P[0] = 0 P[1] = 1 P[2] = 1 P[3] = 1 P[4] = 2 (x≥5) P[x] = P[x-1] + P[x-1-4] * x= 6~8까지는 P[x-1-4] 가 아니라 P[1] ~ P[3] 순으로 더하지만 모두 1로 같으므로 위의 식을 쓸 수 있음 #include using namespace std; int T; int N; long lo..