https://www.acmicpc.net/problem/14699 14699번: 관악산 등산 서울대학교에는 “누가 조국의 미래를 묻거든 고개를 들어 관악을 보게 하라”라는 유명한 문구가 있다. 어느 날 Unused는 Corea에게 조국의 미래를 물었고, Corea는 직접 관악산에 올라가 조국의 미 www.acmicpc.net n번 쉼터에서 출발해서 산을 오를 때 최대로 방문할 수 있는 쉼터의 개수를 구하는 문제다. 쉼터에 도착하면 그 쉼터와 직접 연결된 더 높은 쉼터로 향하는 길들 중 하나를 골라서 그 길을 따라 이동한다. 쉼터의 개수, 쉼터를 연결하는 길의 개수 쉼터의 높이 쉼터를 연결하는 길의 양 끝 쉼터 n번 쉼터에서 출발해서 산을 오를 때 최대로 방문할 수 있는 쉼터의 개수 DP를 이용하여 접근..
DP
https://www.acmicpc.net/problem/20925 20925번: 메이플스토리 첫째 줄 사냥터 수 $N$ ($1 \le N \le 200$)과 방학 기간을 분 단위로 나타낸 $T$ ($1 \le T \le 1\,000$)가 주어진다. 다음 $N$개의 줄에는 $i$번째 사냥터의 특징인 입장에 필요한 최소 경험치 $c_i$와 $1$분마 www.acmicpc.net DP 문제다. 시작점을 입력에 맞춰 체크해줘야 한다. dp 배열은 시간과 위치로 설정했다. dp 배열을 순회하면서 현재 경험치가 0인 곳은 스킵했다. dp의 칸마다 움직일 수 있는 사냥터를 탐색하여 방학이 지나거나 경험치가 모자라는 경우를 제외했다. 이동하는 경우가 아닌 제자리에 머물러 있는 경우는 따로 고려를 했다. #includ..
https://www.acmicpc.net/problem/17498 17498번: 폴짝 게임 첫 번째 줄에 행의 개수 N과 열의 개수 M (2 ≤ N×M ≤ 200,000, 2 ≤ N) 그리고 최대 점프 거리 정수 D (1 ≤ D ≤ 10) 가 주어집니다. i+1 번째 줄에는 i (1 ≤ i ≤ N) 번째 행에 있는 쓰여있는 정수 ai,1, ai,2, www.acmicpc.net DP 문제다. 정적 할당을 하면 배열의 공간 낭비가 심할 것 같아 동적 할당을 했다. (동적 해제는 까먹음) 입력으로 음수가 들어와 점수의 최대 값이 음수가 될 수 있으므로 dp의 초기값을 int 범위의 최솟값으로 지정했다. 지나온 길에서 거리가 d 이하면 점프가 가능하다. 고로 모든 경우의 수의 점프를 고려해야한다. 행을 움직..
https://www.acmicpc.net/problem/2666 2666번: 벽장문의 이동 첫 번째 줄에 벽장의 개수를 나타내는 3보다 크고 20보다 작거나 같은 하나의 정수, 두 번째 줄에 초기에 열려있는 두 개의 벽장을 나타내는 두 개의 정수, 그리고 세 번째 줄에는 사용할 벽장들 www.acmicpc.net DP와 완전 탐색 문제다. DP의 배열을 3차원으로 생성했다. dp[원하는 문을 연 횟수][열린 문 중 왼쪽][열린 문 중 오른쪽] 특정 시점에서 최선의 선택이 다음 선택에서는 최선이 아닐 수도 있기 때문에 완전 탐색을 이용했다. 최대 문의 수가 20이라는 점에서 완전 탐색을 이용해도 시간 초과가 나지 않을 것이라 판단했다. #include #include using namespace std;..
https://www.acmicpc.net/problem/2560 2560번: 짚신벌레 첫째 줄에 a, b, d, N을 나타내는 네 정수가 빈칸 하나를 사이에 두고 차례로 주어진다. 단, 0＜a＜b＜d ≤ 10,000이고, 1 ≤ N ≤ 1,000,000이다. www.acmicpc.net DP와 누적 합 문제다. #include using namespace std; long long dp[1000001]; int main() { // 입출력 속도를 단축시키기 위함 ios::sync_with_stdio(0); cin.tie(0); int a, b, d, N;cin >> a >> b >> d >> N; for (int i = 0; i < a; i++) dp[i] = 1; for (int i = a; i = ..
https://www.acmicpc.net/problem/2225 2225번: 합분해 첫째 줄에 답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net DP 문제다. 처음 생각한 방법은 2차원 배열을 이용해 1을 포함해 1개로 n을 만드는 경우의 수 2를 포함해 1개로 n을 만드는 경우의 수 ... 1을 포함해 2개로 n을 만드는 경우의 수 2를 포함해 2개로 n을 만드는 경우의 수 ... ... ... ... 이렇게 배열 자체를 n을 구하기 위한 경우의 수를 구하려 했다. 겹치는 부분을 생각할 수도 없고 규칙도 찾기 어려워 버렸다. 두 번째 생각한 방법은 모든 경우의 수를 다 적고 거기에서 규칙적인 변화를 찾았다. 작은 규칙을 찾긴 했지만 사용할 수 있는 방법이 없고, ..
