풀이1. 재귀함수를 통해 갈 수 있는 방법에 대해 계속 탐색한다. 2. 계산한 내용을 DP 배열에 저장해 놓는다.3. DP에 저장된 값이 있다면 DP값을 리턴한다. 문제의 내용을 파악하면 조금 풀기 수월하다....재귀 + 메모이제이션으로 해결가능한 문제 이해하기 쉬운 블로그가 있어 링크로 남겨놓습니다.. http://blog.pj-room.com/81 코드12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152#include using namespace std; int n, k, endpoint;int delay_time[1001];int rule[1001][1001];int dp[1001]..

풀이조건을 먼저 살펴보면 다음과 같다. 1. 보물은 육지에 있다. (L에 있다.)2. 이동할 때는 육지로만 갈 수 있다.3. 각 보물의 위치는 육지로 이동하였을 경우 가장 먼거리에 묻혀있다.4. 이동 경로를 카운트 할때는 중복된 지점을 가거나 돌아가는 경우를 제외한다. 조건에 맞춰서 이동하기위해 BFS를 통해 이동할때마다 카운트를 세주면 되는것을 알 수 있다.배열을 돌면서 육지일 경우 해당 지점에 1번 보물이 있다고 가정하고 해당 지점부터 BFS를 돌리면서 가장 멀리 있는 지점 (카운트 값이 가장 큰 지점)에 2번 보물이 있다고 가정한다. MAP을 모두 돌면서 Max 카운트를 비교해서 저장하면 풀 수 있다. 즉, 육지일 경우 카운트가 가장 큰 값을 Max의 경우와 계속 비교하면서 돌아다니면 된다. 소스 ..

풀이모든 경우의 수를 돌리면 시간초과가 나게된다.. 이 문제도 DP를 통해서 구현할 수 있다. (현재값 + DP이전값) 과 (현재값) 중 큰값을 DP배열에 저장해주면서 Max값이랑 비교한다. 1dp[i] = Max(num[i], dp[i - 1] + num[i]);cs--> 이렇게 하면 부분집합의 합을 DP에 계속 쌓을 수 있다. 문제를 해석할 때 놓치는 부분이 있을 수 있다. 입력범위는 -1000 ~ 1000 까지라 int형 내에서 입력을 받을 수 있다. 하지만 입력의 갯수가 n(1≤n≤100,000) 이므로 1000이 연속해서 100000개가 들어와서 DP배열에 쌓게 되면 int형을 벗어날 수 있다. 소스코드12345678910111213141516171819202122232425#include us..

풀이계단 오르기문제랑 비슷한 문제이다. 연속으로 세잔을 마시지 못하는 조건이 들어간것도 똑같다. 모든 경우의 수를 구해서 답을 구할 수 있지만 시간초과가 나므로 DP로 해결할 수 있다. 마실 수 있는 경우의 수를 3가지로 분류할 수 있다.1. 현재 잔을 마셧을 경우2. 이전잔과 현재잔 전전전잔을 마셧을 경우3. 전전잔과 현재잔을 마셧을 경우 이 경우의 수의 최대값을 계속 DP배열에 저장해나가면 해결할 수 있다.1231. dp[i-1]2. wine[i] + wine[i - 1] + dp[i - 3]3. wine[i] + dp[i - 2];cs 소스 코드123456789101112131415161718192021222324252627#include using namespace std; int n, wine[..

풀이조건부터 살펴보면 1. X가 3으로 나누어 떨어지면, 3으로 나눈다.2. X가 2로 나누어 떨어지면, 2로 나눈다.3. 1을 뺀다. 위 순서대로 풀려고하면 예외케이스가 많이 나타나게 된다. 그래서 반대로 생각해보면 DP로 풀 수 있는것을 찾을 수 있다. 1. X에 곱하기 3을 한다.2. X에 곱하기 2를 한다.3. 1을 더한다. cnt=3을 만들어 놓고 cnt를 늘려가면서 계산을 해주면 된다. DP[3*cnt] = DP[cnt]+1DP[2*cnt] = DP[cnt]+1DP[1+cnt] = DP[cnt]+1 이렇게 넣어주되 중복될 경우에는 더작은 숫자를 넣어주면 된다. 문제에서 주어진 크기가 1000000 보다 작거나 같은 수이므로 cnt*3 또는 cnt*2 또는 cnt+1이 1000000을 넘지 않도..

풀이순서대로 우선순위가 주어졌을때 가장큰값을 만나면 큰값을 기준으로 왼쪽에 있는 값이 오른쪽끝으로 넘어가게 된다. 1 2 3 4 가 주어졌을 때 4 1 2 34 3 1 24 3 2 1 순으로 정렬하면 되는것을 알 수 있지만 문서의 우선순위가 같은경우를 체크해주기 위해 chk 배열을 만들면 해결할 수 있다. 문제제목이 큐라고 되어 큐를 구현할수도 있겠지만 우선순위에 맞게 위치를 계속 이동해주면서 최종 배열에서 chk값을 확인하여도 풀 수 있다. 순서1. 0번지를 선택하여 가장 큰값을 찾는다.2. 가장큰값의 index부터 n까지 tmp 배열에 저장해둔다.3. 0부터 가장큰값의 index까지 tmp 배열에 저장해둔다.4. 원래 배열에 tmp배열을 대입한다. 위 순서대로 0부터 n까지 루프를 돌면 내림차순으로 ..