1932 숫자삼각형

백준 1932 숫자삼각형 https://www.acmicpc.net/problem/1932

다음과 같은 규칙을 만족해야 한다.

맨 위층 7부터 시작해서 아래에 있는 수 중 하나를 선택하여 아래층으로 내려올 때, 이제까지 선택된 수의 합이 최대가 되는 경로를 구하는 프로그램을 작성하라. 아래층에 있는 수는 현재 층에서 선택된 수의 대각선 왼쪽 또는 대각선 오른쪽에 있는 것 중에서만 선택할 수 있다.

여기서 샘플을 이용하여 문제를 따라가면 중첩되는 부분을 알 수 있다.

층에서 내려올때의 경우의 수를 먼저 구해보자
경우의 수는 7,3,8/ 7,3,1/ 7,8,1/ 7,8,0 이 나오는데 문제에서는 최대 경로를 구하는 것이므로 이중에서 가운데 있는 부분(3층의 숫자1)은 2가지경우중 더 큰곳에 대해서만 Memoization해 놓으면 된다.

따라서 층입력이 500까지 되므로 cache를 500 * 500 공간으로 잡아서 DP를 시행하면 된다.
DP를 정의하자면
DP[N][M]  : N층 M번째 숫자 까지의 최대 경로

DP[N][1] = DP[N-1][1] + Floor[N][1]
DP[N][N] = DP[N-1][N-1] + Floor[N][N]

for(i = 2; i < N; i++)
     DP[N][i] = max(D[N - 1][i - 1], D[N - 1][i]) + Floor[N][i];

#include <cstdio> #define max(a,b) ((a>b)?a:b) int arr[501][501]; int D[501][501]; int main(){     int N, ans = 0;     scanf("%d", &N);       for (int n = 1; n <= N; n++){         for (int m = 1; m <= n; m++){             scanf("%d", &arr[n][m]);         }         if (n == 1)             D[1][1] = arr[1][1];         else{             D[n][1] = D[n - 1][1] + arr[n][1];             D[n][n] = D[n - 1][n - 1] + arr[n][n];             ans = max(D[n][1], D[n][n]);             for (int k = 2; k < n; k++){                 D[n][k] = max(D[n - 1][k - 1], D[n - 1][k]) + arr[n][k];                 if (n == N)                     ans = max(ans, D[N][k]);             }         }     }     printf("%d\n", ans);     return 0; } Colored by Color Scripter

cs

2579 계단 오르기

백준 2579 계단 오르기 : https://www.acmicpc.net/problem/2579

다음과 같은 규칙을 만족해야한다.

1. 계단은 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다. 즉, 한 계단을 밟으면서 이어서 다음 계단이나, 다음 다음 계단으로 오를 수 있다.
2. 연속된 세 개의 계단을 모두 밟아서는 안된다. 단, 시작점은 계단에 포함되지 않는다.
3. 마지막 도착 계단은 반드시 밟아야 한다.

중요한 사항은 '1. 계단은 한 계단 또는 두 계단을 오를 수 있다.'

                     '2. 세개의 계단을 밟으면 안된다' 이다.

여기서 점화식의 정의를 내리면 다음과 같이 정의할 수 있다.

DP[N][M] :  M계단을 올라갈때 N번째 계단 까지의 총 점수의 최댓값 

중요사항 1번을 토대로 M은 한계단 또는 두 계단 오를 수 있으므로 [1,2] 가 된다.

중요사항 2번째에서 세개의 계단을 밟으면 안되기 때문에 M에 대한 경우를 나눠 

점화식을 완성시킨다.

1. M = 1  

한계단 올라왔을 땐 두 가지 경우로 나뉠 수 있다.

밑의 표를 보면 2번 case는 세 계단을 밟기 때문에 성립하지 않는것을 알 수 있다.

따라서 M = 1일때 N-1번째 계단을 2계단 올라온것(DP[N-1][2])에 현재 계단(Stair[N])을 더해야한다.

DP[N][1] = DP[N-1][2] + Stair[N];

2.  M = 2

두 계단 올라왔을 때도 두 가지 경우로 나뉠 수 있다.

이 경우엔 두 case 모두 성립하므로 두개중 최댓값을 구해 현재 계단과 더하면 된다.

DP[N][2] = max(DP[N-2][1], DP[N-2][2]) + Stair[N];

#include <cstdio> #define max(a,b) ((a>b)?a:b) int main(){     int N, stair[301], DP[301][2] = { 0 };     scanf("%d",&N);     for (int n = 0; n < N; n++)         scanf("%d", &stair[n]);     DP[1][0] = stair[0];     DP[1][1] = 0;     if (N >= 2){         DP[2][0] = stair[0] + stair[1];         DP[2][1] = stair[1];     }     for (int n = 3; n <= N; n++){         DP[n][0] = DP[n - 1][1] + stair[n - 1];         DP[n][1] = max(DP[n - 2][0], DP[n - 2][1]) + stair[n - 1];              }     printf("%d\n",max(DP[N][0], DP[N][1]));     return 0; } Colored by Color Scripter

cs

Min-Max Algortithm

현 오목,장기,체스게임의 주요 인공지능 알고리즘입니다.

저는 장기를 굉장히 좋아하는데 장기를 하는 도중에 중요한 사실을 깨달았습니다.
모든 보드게임에서 상대방을 이길 수 있는 방법은 두가지로 말할 수 있습니다.

1) 상대방보다 더 많은 경우를 보는 것
2) 그에 해당하는 경우에 대해 누가 더 유리한지 판단하는 것

이에 해당하는 논리를 가지고 만들어진 알고리즘이
min-max algorithm입니다.

이 알고리즘은 '최대 최소 이론'이라고도 말합니다. 폰노이만이 만든 알고리즘이며
최대의손실을 최소화 하는 방안이라고 할 수 있으며 이러한 zero sum game에 국한되어
있는 이론을 현 사회의 zero-sum 사회에 맞추어 경제학 이론(Game Theory)을 만들기도
하였습니다.

자세한 min-max algorithm과정은 동영상을 만들었으니 보시는게 나을것 같습니다.
https://www.youtube.com/watch?v=H0jUgUl5vcU