반응형 DP4 [cpp 알고리즘] 백준 20152 Game Addiction [백준] 20152 Game Addiction cpp 풀이알고리즘: 수학, 다이나믹 프로그래밍(DP), 조합론https://www.acmicpc.net/problem/20152문제 요약- 집의 좌표(H,H) 에서 PC 방의 좌표(N,N)가 주어진다.- 좌표평면(x,y)에서 y>x인 곳은 갈 수 없다. - 집에서 PC방까지 경로의 개수를 구해야 한다. (단, 상하좌우 방향으로 이동할 수 있고 한 번 이동할 때 거리는 1이다. 또한 항상 최단 경로로 움직인다.)풀이 정리- 최단경로라는 말에 처음에는 bfs로 생각을 하다가, 뒤로 갈 수록 너무 많고 생각보다 규칙이 보여서 dp로 접근했다.- 아래 사진처럼 예제들을 직접 따라 그려보면 어떻게 구하는지 바로 알 수 있다. (지금 보니까 집이랑 PC방 위치를 반대.. 2024. 7. 15. [cpp 알고리즘] 백준 17291 새끼치기 [백준] 17291 새끼치기 cpp 풀이알고리즘: 구현, 다이나믹 프로그래밍(DP)https://www.acmicpc.net/problem/17291문제 요약아래의 벌레 분열 규칙만 고려해서 코드를 풀이하면 된다. 벌레는 기준년도 1년 2월에 1마리가 탄생한다.벌레는 매년 1월이 되면 분열한다. 분열시 본래의 개체는 그대로, 새로운 개체가 하나 탄생하는 것으로 본다.홀수년도에 탄생한 개체는 3번 분열시, 짝수년도에 탄생한 개체는 4번 분열시 사망한다.이 때, N년 말에 존재하는 벌레의 수를 구하면 된다. 풀이 정리- 기준년도 1년 2월 = 1 마리- 2년 1월 = 1 + 1(새로 분열)- 3년 1월 = 1 + 1 + 2(새로 분열) - 4년 1월 = 1 + 1 + 2 + 4(새로 분열) - 1(기준년도.. 2024. 7. 7. [cpp 알고리즘] 백준 10942 팰린드롬? [백준] 10942 팰린드롬? cpp 풀이 DP, 다이나믹 프로그래밍 문제 출처: https://www.acmicpc.net/problem/10942 10942번: 팰린드롬? 총 M개의 줄에 걸쳐 홍준이의 질문에 대한 명우의 답을 입력으로 주어진 순서에 따라서 출력한다. 팰린드롬인 경우에는 1, 아닌 경우에는 0을 출력한다. www.acmicpc.net 문제 요약 - 자연수 N개(1> M; for(int i=1; i s >> e; if(dp[s][e] == 1) cout 2023. 5. 6. [cpp 알고리즘] 백준 1149 RGB거리 c++ 1. 문제 2. 풀이 3. 코드 #include #include using namespace std; int N; int arr[1001][3]; int dp[1001][3]; int main(){ // input cin >> N; for(int i=0; i arr[i][j]; } } // init dp[0][0] = arr[0][0]; dp[0][1] = arr[0][1]; dp[0][2] = arr[0][2]; // dp[x][0] = arr[x][0] + min(dp[x-1][1], dp[x-1][2]) for(int i=1; i 2022. 7. 13. 이전 1 다음 반응형
