소스 코드12345678910111213141516171819202122#include using namespace std; int n,p[1001],dp[1001]; int returnMax(int a, int b) { return a > b ? a : b;} int main() { cin >> n; for (int i = 1; i > p[i]; } for (int i = 1; i

풀이2xn 타일링 문제에서 타일이 하나더 늘어난 형태의 문제다. 2xn 타일링 문제를 풀때와 동일하게 DP를 이용하고 DP배열의 크기를 크게 잡아주어야 한다. 다만 타일이 하나가 더늘어 났기때문에 점화식을 수정해주어야한다. 1x2, 2x1, 2x2 타일로 채우는 경우의 수를 구할 때 가로 크기가 2인 타일이 하나가 더추가되었다. i번째 타일의 경우는 i-1번째에서 1x2짜리 타일 한개붙이는 경우와 i-2번째에서 2x1 타일 두개 붙이는 경우와 2x2 타일 한개를 붙이는 경우가 있다. 즉, dp[i] = dp[i-1] + dp[i-2]*2 을 도출할 수 있다. 소스 코드12345678910111213141516#include using namespace std; int n;long long dp[1001]..

풀이STL을 사용하면 매우 간단하게 구현할 수 있다. STL을 사용하지 않고 풀어보기 위해서는 먼저 규칙성을 찾아야한다. N=31 2 31 3 22 1 32 3 13 1 23 2 1 N=41 2 3 41 2 4 31 3 2 41 3 4 21 4 2 31 4 3 22 1 3 42 1 4 32 3 1 4 2 3 4 12 4 1 32 4 3 13 1 2 43 1 4 23 2 1 43 2 4 13 4 1 23 4 2 14 1 2 34 1 3 24 2 1 34 2 3 14 3 1 24 3 2 1 N=3일경우에는 규칙을 비교할 수 있는 데이터양이 적어서 N=4인 경우 규칙성을 찾아보기가 조금 쉽다.. 규칙1. 오른쪽에서 왼쪽으로 이동하면서 n과 n-1을 비교한다.2. n-1 12 543 123645987 --> 1..

풀이 7576번 문제랑 똑같은데 Z축이 하나더 추가된 문제이다. 기본적인 BFS로 풀면서 한번 갈때마다 카운트를 세주면 풀 수 있는 문제 Z축을 [a][b][c] 중 a로할지 c로 할지 잘 정해주고, Que사이즈, 입력받는 배열의 사이즈만 잘 고려해주면 된다. 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 ..

풀이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의 경우와 계속 비교하면서 돌아다니면 된다. 소스 ..