꾸준함

문제 링크입니다: https://www.acmicpc.net/problem/2169기존에 풀었던 DP 문제들은 오른쪽 혹은 아래만 갈 수 있어 재방문 여부를 확인하지 않아도 됬는데 해당 문제는 왼쪽도 고려해야했기 때문에 난이도가 다른 문제들보다는 있었던 문제였던 것 같습니다.visited[col][row]를 통해 방문 여부를 적절히 표시하는 것이 핵심이였습니다.(조합 구하는 재귀함수와 비슷) #include #include #include //memsetusing namespace std; const long long MININF = -2e9;const int MAX = 1000; int N, M; //세로 가로int Mars[MAX][MAX];bool visited[MAX][MAX];long long ..

문제 링크입니다: https://www.acmicpc.net/problem/5557왼쪽에서부터 차근차근 연산해가며 조건이 맞는지 확인하면 쉽게 풀 수 있는 문제였습니다. #include #include //memset using namespace std; const int MAX = 100; int N; int operand[MAX]; //피연산자 집합 long long cache[20 + 1][MAX]; //연산 결과인 0~20, idx long long numOfWays(int leftNum, int idx) //왼쪽에서부터 연산을 시작하므로 leftNum, idx는 여태까지 연산을 진행한 인덱스 { //기저 사례 if (leftNum 20) return 0; if (idx..

문제 링크입니다: https://www.acmicpc.net/problem/1495'계산 한적 없다'와 '불가능'한 경우를 다른 숫자로 표현하는 것이 핵심이였습니다.둘 다 -1로 표현한다면 메모이제이션이 정상적으로 처리하지 못하여 시간초과가 발생하기 때문입니다. #include #include #include //memset using namespace std; const int MAX = 100; const int MAXV = 1000; //최대 볼륨 int N, S, M; //곡의 수, 시작할 때 볼륨, 최대 볼륨 int playlist[MAX + 1]; int cache[MAXV + 1][MAX + 1]; int maxVolume(int volume, int idx) //현재 소리, 노래 번호 { ..

문제 링크입니다: https://www.acmicpc.net/problem/2240해당 시점에서 자리를 바꿀 경우와 그대로 있는 경우를 모두 고려하여 계산하면 답을 구할 수 있습니다. #include #include #include //memsetusing namespace std; const int MAX = 1000;const int MOVE = 30 + 1; int T, W;int plum[MAX];int cache[3][MAX][MOVE]; int maxPlum(int tree, int second, int move) //나무 번호, 초, 움직인 횟수{ //기저사례 if (second == T) return 0; int &result = cache[tree][second][move]; if (re..

문제 링크입니다: https://www.acmicpc.net/problem/9084http://jaimemin.tistory.com/362과 동일한 문제였습니다. /* 우리나라 화폐단위, 특히 동전에는 1원, 5원, 10원, 50원, 100원, 500원이 있다. 이 동전들로는 모두 정수의 금액을 만들 수 있으며 그 방법도 여러 가지가 있을 수 있다. 예를 들어, 30원을 만들기 위해서는 1원짜리 30개 또는 10원짜리 2개와 5원짜리 2개 등의 방법이 가능하다. 동전의 종류가 주어질 때에 주어진 금액을 만드는 모든 방법을 세는 프로그램을 작성하시오. */ #include #include //memset using namespace std; const int MAX = 20; const int MONEY ..

문제 링크입니다: https://www.acmicpc.net/problem/11060간단한 메모이제이션을 이용하면 쉽게 풀 수 있는 문제였습니다.최대 arr[i]만큼 움직이는 것이므로 1부터 arr[i]만큼 움직여보는 것이 핵심이였습니다. #include #include #include //memset using namespace std; const int INF = 987654321; const int MAX = 1000; int N; int arr[MAX]; int cache[MAX]; int minJump(int start) { if (start == N - 1) //목적지 도달할 경우 return 0; if (start >= N) //목적지 도달 못할 경우 return INF; int &resul..

문제 링크입니다: https://www.acmicpc.net/problem/2302좌석 수 별로 경우의 수를 구하다 보면 간단히 피보나치 수열인 것을 확인할 수 있다.피보나치 수열인 이유는 1. i번째 좌석에 i번 티켓을 가진 사람이 앉게 된다면 i-1개의 좌석의 경우의 수가 되고2. i번째 좌석에 i-1번 티켓을 가진 사람이 앉게 된다면 i-1번 좌석에는 i번 티켓을 가진 사람이 앉게 되므로 i-2개의 좌석의 경우의 수가 된다. 따라서 VIP 좌석이 있다면 0~첫번째 VIP 좌석 사이에 있는 좌석의 수번째 피보나치 수열, 첫번째 VIP 좌석과 두번째 VIP 좌석 사이에 있는 좌석의 수번째 피보나치 수열, ..., i번째 VIP 좌석과 i+1번째 VIP 좌석 사이에 있는 좌석의 수번째 피보나치 수열을 모..

문제 링크입니다: https://www.acmicpc.net/problem/2098http://jaimemin.tistory.com/365와 비슷한 문제였습니다.다른점은 다시 해당 도시로 돌아오는 경로도 더해줘야하고 (i,j)와 (j,i)가 대칭이 아니라는 점이였습니다. #include #include #include //memset using namespace std; const int MAX = 16; const int INF = 987654321; int N; int W[MAX][MAX]; int cache[MAX][1 W[i][j]; int result = INF; memset(cache, -1, sizeof(cache)); cout

문제 링크입니다: https://www.acmicpc.net/problem/2631http://jaimemin.tistory.com/430와 비슷하게 LIS를 떠올리는 것이 핵심인 문제였습니다.결국 어린이들 중 정렬이 안되있는 어린이들만 정렬하면 되므로 (총 어린이 수 - 최대 증가 순열)을 구하면 되는 문제였습니다. #include #include #include //memset using namespace std; const int MAX = 200; int N; int arr[MAX]; int cache[MAX + 1]; int LIS(int start) //Longest Increasing Sequence { int &result = cache[start + 1]; if (result != -1)..

문제 링크입니다: https://www.acmicpc.net/problem/10164이산수학에서 배운 조합을 쓴다면 훨씬 간단하게 풀 수 있는 문제입니다.하지만 동적계획법을 연습하고 싶은 관계로 다음과 같이 풀었습니다.*(x+1)+y*M이 격자 안에 있는 숫자입니다. #include #include //memsetusing namespace std; const int MAX = 15; int N, M, K; //두 정수, o로 표시된 칸의 번호int arr[MAX][MAX];long long cache[MAX][MAX]; //(x+1)+y*M -> 격자 안에 있는 숫자long long path(int y, int x){ //기저 사례 if (y == N - 1 && x == M - 1) //목적지에 도달..