본문 바로가기

728x90

알고리즘 문제 풀이/DP19

[백준]1520번: 내리막 길 https://www.acmicpc.net/problem/1520 1520번: 내리막 길 여행을 떠난 세준이는 지도를 하나 구하였다. 이 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 한 칸은 한 지점을 나타내는데 각 칸에는 그 지점의 높이가 쓰여 있으 www.acmicpc.net 이거... 나한테는 너무 어려웠다... 오래 고민하고 힌트 봐도 잘 모르겠어서 다른 분들 풀이를 아주 많이 참고했음 다른 분들 풀이 볼때에도 이해하는 데 좀 오래 걸렸당...ㅎ 결론부터 말하자면 이 문제는 dfs + dp 문제다 현재 칸으로부터 도착점까지 이동하는 경로의 수는 인접한 칸(상하좌우, 최대 4개)을 시작점으로 도착점까지 이동하는 경로의 수들의 합이다. 각 칸을 시작점으로 도착점까지 이동할 .. 2023. 2. 17.

[백준]1890번: 점프 https://www.acmicpc.net/problem/1890 1890번: 점프 첫째 줄에 게임 판의 크기 N (4 ≤ N ≤ 100)이 주어진다. 그 다음 N개 줄에는 각 칸에 적혀져 있는 수가 N개씩 주어진다. 칸에 적혀있는 수는 0보다 크거나 같고, 9보다 작거나 같은 정수이며, 가장 www.acmicpc.net 처음에는 방문했던 점을 큐에다가 넣어가면서 단순 탐색을 했었는데 자꾸 메모리 초과가 됐다 찾아보니까 단순탐색, dfs, bfs로 풀면 시간이나 메모리 초과가 나는 문제였다 그래서 dp로 풀었음!! #include using namespace std; int n; int arr[101][101]; long dp[101][101]; //경로의 개수는 최대 2^63 - 1 까지다. (int범.. 2023. 2. 14.

[백준]11048번: 이동하기 https://www.acmicpc.net/problem/11048 11048번: 이동하기 준규는 N×M 크기의 미로에 갇혀있다. 미로는 1×1크기의 방으로 나누어져 있고, 각 방에는 사탕이 놓여져 있다. 미로의 가장 왼쪽 윗 방은 (1, 1)이고, 가장 오른쪽 아랫 방은 (N, M)이다. 준규는 www.acmicpc.net 너무 BFS 문제처럼 생겼지만 bfs로 풀면 메모리 초과가 난다 이 문제는 한 칸으로부터 이동할 수 있는 칸이 최대 3개로 제한되어 있고, 최단 거리를 구하는 문제도 아니기 때문에 dp로 풀면 댄다 dp문제인걸 알고 풀면 아주 쉽다 첫번째 예제를 가지고 풀어보자 배열을 2개 만들어준다. maze에는 놓여있는 사탕 수를, dp에는 획득한 사탕 수의 최대를 저장할거다 한 칸씩 이동하면서.. 2023. 2. 12.

[백준]10844번: 쉬운 계단수 https://www.acmicpc.net/problem/10844 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net dp문제! i \ j 1 2 3 4 5 6 7 8 9 1 1 1 1 1 1 1 1 1 1 2 2 dp[i][j]에서 i는 자릿수를, j는 시작 숫자를 의미한다. 예시 - dp[2][4] : 4로 시작하는 2자리 숫자. 총 2개 (43,45) 1) 한자리 숫자는 모두 계단수 2) n자리 숫자 1로 시작 - 10xxxx... , 12xxxx... 두가지 경우 가능 - 전자의 경우, 계단수를 만드려면 101xxxx... 가 되어야 함 - 따라서 경우의 수는 1로 시작하는 n-2자리 숫자의 개수인데 이 값이 dp[i-.. 2023. 2. 11.

[백준] 11057번 : 오르막 수 https://www.acmicpc.net/problem/11057 11057번: 오르막 수 오르막 수는 수의 자리가 오름차순을 이루는 수를 말한다. 이때, 인접한 수가 같아도 오름차순으로 친다. 예를 들어, 2234와 3678, 11119는 오르막 수이지만, 2232, 3676, 91111은 오르막 수가 아니다. 수 www.acmicpc.net DP 문제!! 조건에 따라 오르막 숫자의 개수를 아래와 같이 계산해보면, 0으로끝남 1로끝남 2로끝남 3으로끝남 4로끝남 5로끝남 6으로끝남 7로끝남 8로끝남 9로끝남 0 - - - - - - - - - - 1자리숫자 1 1 1 1 1 1 1 1 1 1 2자리숫자 1 2 3 4 5 6 7 8 9 10 3자리숫자 1 3 6 10 15 21 28 36 45 55 규.. 2023. 2. 10.

[백준] 1463번 : 1로 만들기 https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 정수 N을 1로 만들기 위해서 사용할 수 있는 연산은 다음 세 가지이다. 편의상 연산 A, B, C라고 하겠다 연산A N이 3으로 나누어 떨어지면, 3으로 나눈다. 연산B N이 2로 나누어 떨어지면, 2로 나눈다. 연산C 1을 뺀다. 정수 N이 2인 경우 연산A: 불가능하다 연산B: 2 / 1 = 1이므로 1이 만들어진다. (연산횟수:1) 연산C: 2 - 1 = 1이므로 1이 만들어진다. (연산횟수:1) 최소 연산 횟수는 1이다. 정수 N이 3인 경우 연산A: 3 / 1 = 1이므로 1이 만들어진다. (연산횟수.. 2023. 1. 20.

이전 1 2 3 4 다음

728x90

티스토리툴바