🔍 DP

---

📌 1. DP, DPS, BFS 시간 비교

백준 1463번

Dp : 4ms, 메모리 : 4900 KB

코드 보기

#include<stdio.h>

#define N_MAX 1000001
#define Min(a,b) ((a<b)?a:b)

int main() {
	int N;
	scanf("%d", &N);

	
	int dp[N_MAX];
	
	dp[1] = 0;

	for (int i = 2;i <= N;i++) {
		//가장 간단한 경우로 초기화
		//셋 중 최소 횟수로 dp배열에 삽입
		dp[i] = dp[i - 1] + 1;
		if (i % 2 == 0) dp[i] = Min(dp[i], dp[i / 2] + 1);
		if (i % 3 == 0) dp[i] = Min(dp[i], dp[i / 3] + 1);

		//printf("dp[%d] : %d\n", i, dp[i]);
	}

	printf("%d\n", dp[N]);

	return 0;
}

my_Dfs : 64ms, 메모리 : 51772 KB

코드 보기

#include <stdio.h>
#include <limits.h>

#define MAX_N 1000000

int min_step = INT_MAX; // 최소 연산 수 저장
int visited[MAX_N + 1] = { 0 }; // 각 값의 최소 연산 횟수 기록

void dfs(int n, int step) {

    //printf("cur : %d | step : %d\n", n, step);
    // 숫자가 1이면 최소 연산 수 갱신
    if (n == 1) {
        if (step < min_step) {
            min_step = step;
        }
        return;
    }

    //시간 줄이기 위한
    // 이미 방문했거나, 현재 연산이 최소 연산 이상인 경우 탐색 중단
    if (visited[n] && step >= visited[n]) {
        return;
    }
    visited[n] = step; // 현재 상태 방문 기록


    // 가능한 연산 수행
    if (n % 3 == 0) {
        dfs(n / 3, step + 1);
    }
    if (n % 2 == 0) {
        dfs(n / 2, step + 1);
    }
    dfs(n - 1, step + 1); // 항상 가능
}

int main() {
    int N;
    scanf("%d", &N);

    dfs(N, 0);

    printf("%d\n", min_step);

    return 0;
}

Dfs : 8ms, 메모리 : 5016 KB

코드 보기

#include <stdio.h>
#include <limits.h>

#define MAX_N 1000000

int min_step = INT_MAX; // 최소 연산 수 저장
int visited[MAX_N + 1] = {0}; // 방문 여부 기록

void dfs(int n, int step) {

    //printf("cur : %d | step : %d\n", n, step);
    // 숫자가 1이면 최소 연산 수 갱신
    if (n == 1) {
        if (step < min_step) {
            min_step = step;
        }
        return;
    }

    // 이미 방문했거나, 현재 연산이 최소 연산 이상인 경우 탐색 중단
    if (visited[n] && step >= visited[n]) {
        return;
    }

    visited[n] = step; // 현재 상태 방문 기록

    // 가능한 연산 수행
    if (n % 3 == 0) {
        dfs(n / 3, step + 1);
    }
    if (n % 2 == 0) {
        dfs(n / 2, step + 1);
    }
    dfs(n - 1, step + 1); // 항상 가능
}

int main() {
    int N;
    scanf("%d", &N);

    dfs(N, 0);

    printf("%d\n", min_step);

    return 0;
}

BFS : 0ms, 메모리 : 9784 KB

코드 보기

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

#define MAX_N 1000000

typedef struct {
    int n;      // 현재 숫자
    int step;   // 현재까지 수행한 연산 수
} Node;

int bfs(int start) {
    bool visited[MAX_N + 1] = {false}; // 방문 여부 기록
    Node queue[MAX_N];
    int front = 0, rear = 0;

    // 초기 상태 삽입
    queue[rear++] = (Node) {start, 0};
    visited[start] = true;

    while (front < rear) {
        Node cur = queue[front++];
        
        // 숫자가 1이 되면 최소 단계를 반환
        if (cur.n == 1) {
            return cur.step;
        }

        // 가능한 다음 상태 삽입
        if (cur.n % 3 == 0 && !visited[cur.n / 3]) {
            queue[rear++] = (Node) {cur.n / 3, cur.step + 1};
            visited[cur.n / 3] = true;
        }
        if (cur.n % 2 == 0 && !visited[cur.n / 2]) {
            queue[rear++] = (Node) {cur.n / 2, cur.step + 1};
            visited[cur.n / 2] = true;
        }
        if (cur.n - 1 > 0 && !visited[cur.n - 1]) {
            queue[rear++] = (Node) {cur.n - 1, cur.step + 1};
            visited[cur.n - 1] = true;
        }
    }

    return -1; // 도달할 수 없는 경우
}

int main() {
    int N;
    scanf("%d", &N);

    int result = bfs(N);
    printf("%d\n", result);

    return 0;
}

---

📌 2. 사칙연산 DP

백준 9095번

코드 보기

#include<stdio.h>

#define MAX 11

int dp[MAX];

void sol() {
	dp[1] = 1;	// 1
	dp[2] = 2;	// 1+1, 2
	dp[3] = 4;	// 1+1+1, 1+2, 2+1, 3

	for (int i = 4;i < MAX;i++) {
		dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3];
	}
}
int main() {
	int T;
	scanf("%d", &T);

	sol();

	for (int i = 0;i < T;i++) {
		int n;
		scanf("%d", &n);

		int res = dp[n];
		printf("%d\n", res);
	}

	return 0;
}

초기값 : dp[1], dp[2], dp[3] 점화식 : dp[i] = dp[i-1] + dp[i-2] + dp[i-3]

---

📌 3. 계단 오르면서 점수 따기 DP

백준 2579번

코드 보기

#include<stdio.h>

#define MAX 301
#define Max(a,b) ((a>b)?a:b)

int main() {
	int n;
	scanf("%d", &n);

	int score[MAX];
	for (int i = 1;i <= n;i++) {
		scanf("%d", &score[i]);
	}

	int dp[MAX];

	// 연속된 세 개의 계단을 모두 밟으면 안되기에
	dp[1] = score[1];
	dp[2] = score[2] + score[1];
	int temp1 = score[1] + score[3];
	int temp2 = score[2] + score[3];
	dp[3] = Max(temp1, temp2);

	for (int i = 4;i <= n;i++) {
		// 1) 낮은,		높은, 다음
		// 2)		중간,	  다음
		temp1 = dp[i - 3] + score[i - 1] + score[i];
		temp2 = dp[i - 2] + score[i];
		dp[i] = Max(temp1, temp2);
		//printf(" temp1 : %d | temp2 : %d\n", temp1, temp2);
		//printf("dp[%d] : %d\n", i, dp[i]);
	}
	printf("%d\n", dp[n]);

	return 0;
}

---

📌 4. 최소 비용 계산 (집 RGB 색칠하기)

백준 1149번

코드 보기

#include<stdio.h>

#define MAX 1001
//#define Min(a,b) ((a<b)?a:b)

int Min(int a, int b) {
	int temp = a < b ? a : b;
	return temp;
}
int main() {
	int N;
	scanf("%d", &N);

	int dp[MAX][3];
	int cost[MAX][3];
	for (int i = 1;i <= N;i++) {
		scanf("%d %d %d", &cost[i][0], &cost[i][1], &cost[i][2]);
	}

	// DP 초기값 : 1번집 3가지 경우
	for (int i = 0;i < 3;i++) {
		dp[1][i] = cost[1][i];
	}
	
	// DP 점화식
	// 현재 각 색의 최소 비용 = 현재 색 비용 + 이전 다른색 최소 비용
	for (int i = 2;i <= N;i++) {
		dp[i][0] = cost[i][0] + Min(dp[i - 1][1], dp[i - 1][2]);	// R
		dp[i][1] = cost[i][1] + Min(dp[i - 1][0], dp[i - 1][2]);	// G
		dp[i][2] = cost[i][2] + Min(dp[i - 1][0], dp[i - 1][1]);	// B
	}

	int res = Min(dp[N][0], Min(dp[N][1], dp[N][2]));
	printf("%d\n", res);

	return 0;
}

---

📌 5. 2xn 직사각형 채우기

백준 11726번

코드 보기

#include<stdio.h>

#define MAX 1001
#define MOD 10007

int main() {
	int n;
	scanf("%d", &n);

	// dp[i] 2xi 의 직사각형
	int dp[MAX];

	// 초기값
	dp[1] = 1;	// 세로 1
	dp[2] = 2;	// 세로 2 or 가로 2

	for (int i = 3;i <= n;i++) {
		// dp[i-1] : 직사각형 1칸을 더 채우기 위해 이전 상태에서 1x2 추가한 방법
        // dp[i-2] : 직사각형 2칸을 더 채우기 위해 이전 상태에서 2x2 추가한 방법
		dp[i] = (dp[i - 1] + dp[i - 2]) % MOD;
	}

	printf("%d\n", dp[n]);

	return 0;
}

---

📌 6. 구간 합 구하기

백준 11659번

코드 보기

#include<stdio.h>

#define MAX 100001

int main() {

	int N, M;
	scanf("%d %d", &N, &M);

	int num[MAX];

	// dp[i] : 1번째부터 i번째까지의 합
	int dp[MAX];
	int sum = 0;
	for (int i = 1;i <= N;i++) {
		scanf("%d", &num[i]);
		sum += num[i];
		dp[i] = sum;
	}

	for (int i = 0;i < M;i++) {
		int a, b;
		scanf("%d %d", &a, &b);

		// a번째 ~ b번째까지 합
		printf("%d\n", dp[b] - dp[a] + num[a]);
	}

	return 0;
}

---

📌 7. 1로 만들기 2 : 어디서 왔는지 기억

백준 12852번

코드 보기

#include<stdio.h>

#define MAX (1000001)
#define Min(a,b) ((a<b)?a:b)

int main() {
	int N;
	scanf("%d", &N);

    int dp[MAX] = { 0 }; // dp 배열 초기화
    int prev[MAX];  //어디서 왔는지 기억

    int check = 0;
    for (int i = 2; i <= N; i++) {
        dp[i] = dp[i - 1] + 1; // 1을 뺀 경우
        prev[i] = i - 1;        //i-1에서 옴

        if (i % 2 == 0) {
            if (dp[i] > dp[i / 2] + 1) {
                dp[i] = dp[i / 2] + 1;
                prev[i] = i / 2;    //i/2에서 옴
            }
        }
        if (i % 3 == 0) {
            if (dp[i] > dp[i / 3] + 1) {
                dp[i] = dp[i / 3] + 1;
                prev[i] = i / 3;    //i/3에서 옴
            }
        }
    }

	printf("%d\n", dp[N]);

    int i = N;
    while (i >= 1) {
        printf("%d ", i);
        i = prev[i];
    }

	return 0;
}

---

📌 8. 피보나치 수열 : dp[n]은 1의 출력 횟수, dp[n-1]은 0의 출력 횟수

백준 1003번번

코드 보기

#include<stdio.h>
#include<stdbool.h>

#define MAX 41
int dp[MAX];
bool visited[MAX];

int fibonacci(int n) {
	if (n == 0) {
		printf("0");
		return 0;
	}
	else if (n == 1) {
		printf("1");
		return 1;
	}
	else {
		return fibonacci(n - 1) + fibonacci(n - 2);
	}
}
void fibo(int n) {
	for (int i = 2;i <= n;i++) {
		dp[i] = dp[i - 1] + dp[i - 2];
		visited[i] = 1;
		//printf("dp[%d] : %d\n", i, dp[i]);
	}
}
void print(int n) {
	if (n == 0)
		printf("%d %d\n", 1, 0);
	else 
		// 0 출력 횟수 : dp[n-1] , 1 출력 횟수 : dp[n]
		printf("%d %d\n", dp[n-1], dp[n]);
}
void init() {
	dp[0] = 0;
	dp[1] = 1;
	visited[0] = 1;
	visited[1] = 1;
}
int main() {
	int T;
	scanf("%d", &T);

	init();
	for (int i = 0;i < T;i++) {
		int n;
		scanf("%d", &n);

		if (!visited[n]) {
			fibo(n);
		}
		print(n);
	}

	return 0;
}

---

📌 9. 삼각형 내려가며 더하기

백준 1932번

복잡

코드 보기

#include<stdio.h>

#define MAX 501
#define Maxab(a,b) ((a>b)?a:b)

typedef struct {
    int x;
    int y;
}Pos;

int dx[2] = { -1, -1 };
int dy[2] = { -1, 0 };
int map[MAX][MAX] = { 0 };

void print(int n, int dp[][MAX]) {
    for (int i = 0;i < n;i++) {
        for (int j = 0;j < (i + 1);j++) {
            printf("%d ", dp[i][j]);
        }
        printf("\n");
    }
}
int main() {
    int n;
    scanf("%d", &n);
    
    for (int i = 0;i < n;i++) {
        for (int j = 0;j < (i + 1);j++) {
            scanf("%d", &map[i][j]);
        }
    }

    int dp[MAX][MAX] = {0};
    dp[0][0] = map[0][0];
    for (int i = 0;i < n;i++) {
        for (int j = 0;j < (i + 1);j++) {
            Pos cur = { i,j };
            for (int k = 0;k < 2;k++) {
                Pos prev = { cur.x + dx[k], cur.y + dy[k] };
                //printf("prev  : %d %d\n", prev.x, prev.y);
                if (prev.x >= 0 && prev.y >= 0 && prev.y < (i + 1)) {
                    dp[i][j] = Maxab(dp[i][j], dp[prev.x][prev.y]+map[i][j]);
                    //printf("dp[%d][%d]  : %d\n",i, j, dp[i][j]);
                }
            }

        }
    }
    
    //print(n, dp);

    int res = 0;
    for (int j = 0;j < n;j++) {
        res = Maxab(res, dp[n-1][j]);
    }
    printf("%d\n", res);


    return 0;
}

단순

코드 보기

#include<stdio.h>

#define MAX 500
#define Maxab(a,b) ((a>b)?a:b)

int dp[MAX][MAX];
int tri[MAX][MAX];

void print(int n) {
    for (int i = 0;i < n;i++) {
        for (int j = 0;j < i + 1;j++) {
            printf("%d ", dp[i][j]);
        }
        printf("\n");
    }
}
int main() {
    int n;
    scanf("%d", &n);

    for (int i = 0; i < n; i++) {
        for (int j = 0; j <= i; j++) {
            scanf("%d", &tri[i][j]);
        }
    }

    // 초기 값
    dp[0][0] = tri[0][0];

    // DP 테이블 채우기
    for (int i = 1; i < n; i++) {
        for (int j = 0; j <= i; j++) {
            if (j == 0) {   //왼쪽 끝
                dp[i][j] = dp[i - 1][j] + tri[i][j];
            }
            else {          //이외에
                dp[i][j] = tri[i][j] + Maxab(dp[i - 1][j - 1], dp[i - 1][j]);
            }
        }
    }
    
    print(n);

    // 최댓값 출력
    int max_sum = dp[n - 1][0];
    for (int j = 1; j < n; j++) {
        if (dp[n - 1][j] > max_sum) {
            max_sum = dp[n - 1][j];
        }
    }

    printf("%d\n", max_sum);

    return 0;
}

---

📌 10. 2xn 직사각형 채우기2

백준 11727번

코드 보기

#include<stdio.h>

#define MOD 10007
#define MAX 1001

int main() {
	int n;
	scanf("%d", &n);

	int dp[MAX] = { 0 };
	dp[1] = 1;
	dp[2] = 3;

	for (int i = 3;i <= n;i++) {
		//   dp[i-1] : 가로 1 잡아먹는 경우의 수 : 직사각형의 한쪽에 1x2 추가
		// 2*dp[i-2] : 가로 2 잡아먹는 경우의 수
		dp[i] = (dp[i - 1] + 2*dp[i - 2]) % MOD;
	}

	printf("%d\n", dp[n]);

	return 0;
}

---

📌 11. 이찬수 : 0으로 끝나는 수, 1로 끝나는 수 나눠서 생각

백준 2193번

코드 보기

#include<stdio.h>

#define MAX 91

int main() {

	int N;
	scanf("%d", &N);

	long long int dp_one[MAX] = { 0 };	//1로 끝나는 이찬수
	long long int dp_zero[MAX] = { 0 };	//0으로 끝나는 이찬수
	dp_one[1] = 1;	//1
	dp_one[2] = 0;
	dp_zero[1] = 0;
	dp_zero[2] = 1;	//10
	for (int i = 3;i <= N;i++) {
		dp_one[i] = dp_zero[i - 1];
		dp_zero[i] = dp_one[i - 1] + dp_zero[i - 1];
	}

	printf("%lld\n", dp_one[N] + dp_zero[N]);
	return 0;
}

코드 보기

#include<stdio.h>

#define MAX 91

int main() {
    int n;
    scanf("%d", &n);

    int dp[MAX] = { 0 };
    dp[1] = 1;
    dp[2] = 2;

    for (int i = 3; i <= n; i++) {
        //dp[i-1] : 0으로 끝나는 이찬수, 1자리만 비어있으면 됨
        //dp[i-2] : 1로 끝나는 이찬수, 2자리가 비어있어야 함
        dp[i] = dp[i - 1] + dp[i - 2];
    }

    printf("%d\n", dp[n]);

    return 0;
}

---

📌 12. 연속합 : 나열된 수 중 연속된 부분 최대합 구하기 : 아이디어 필요

백준 1912번

코드 보기

#include <stdio.h>

#define MAX 100001

int max_subarray_sum(int arr[], int n) {
	int max_sum = arr[0];
	int current_sum = arr[0];

	for (int i = 1; i < n; i++) {
        // 현재 수가 양수면 더하고, 음수는 해당 수로
		current_sum = (current_sum > 0) ? (current_sum + arr[i]) : arr[i];
		//printf("%d\n", current_sum);
		if (current_sum > max_sum) {
			max_sum = current_sum;
		}
	}

	return max_sum;
}

int main() {
	int n;
	scanf("%d", &n);

	int arr[MAX];
	for (int i = 0; i < n; i++) {
		scanf("%d", &arr[i]);
	}

	printf("%d\n", max_subarray_sum(arr, n));

	return 0;
}

---

📌 13. 어째서…?

백준 11055번

코드 보기

#include <stdio.h>

int max_increasing_subsequence_sum(int arr[], int n) {
	int dp[n]; // dp[i]는 i번째 요소까지 증가하는 부분 수열의 최대 합
	dp[0] = arr[0];

	for (int i = 1; i < n; i++) {
		dp[i] = arr[i]; // 최소값 초기화
		for (int j = 0; j < i; j++) {
			if (arr[i] > arr[j]) {
				dp[i] = (dp[i] > dp[j] + arr[i]) ? dp[i] : (dp[j] + arr[i]);
			}
		}
	}

	int max_sum = dp[0];
	for (int i = 1; i < n; i++) {
		if (dp[i] > max_sum) {
			max_sum = dp[i];
		}
	}

	return max_sum;
}

int main() {
	int n;
	scanf("%d", &n);

	int arr[n];
	for (int i = 0; i < n; i++) {
		scanf("%d", &arr[i]);
	}

	printf("%d\n", max_increasing_subsequence_sum(arr, n));

	return 0;
}

---

📌 14. 가장 긴 증가하는 부분 수열

백준 11053

코드 보기

#include<stdio.h>

#define N_MAX 1001
#define Max(a,b) ((a>b)?a:b)

int main() {
	int N;
	scanf("%d", &N);

	int A[N_MAX];
	for (int i = 1;i <= N;i++) scanf("%d", &A[i]);
	
	int dp[N_MAX] = { 0 };  //처음부터 i번째까지 가장 긴 길이를 저장할 배열
	dp[1] = 1; //A[1];	//초기값

	for (int i = 2;i <= N;i++) {
		dp[i] = 1; //A[i];	//기본값 A[i]가 제일 클 때 : 길이 1
		for (int j = 1;j < i;j++) {
			if (A[i] > A[j]) {
				//현재까지 알고 있던 최대 길이와 새로 수정된 + A[i]을 포함시킨 것(1) 중 더 긴 길이를 저장
				dp[i] = Max(dp[i], dp[j] + 1);
				
				//dp[i] = Max(dp[i], dp[j] + A[i]);
				//printf("dp[%d] : %d\n",i, dp[i]);
			}
		}
	}

	//가장 긴 길이 찾기
	int max_len = 0;
	for (int i = 1;i <= N;i++) {
		if (dp[i] > max_len) max_len = dp[i];
	}

	printf("%d\n", max_len);
	return 0;
}

---

📌 15. 파도반 수열

백준 9461번

코드 보기

#include<stdio.h>

#define MAX 101

int main() {
	int T;
	scanf("%d", &T);

	for (int i = 0;i < T;i++) {
		int N;
		scanf("%d", &N);

		long long int P[MAX];
		P[1] = 1;
		P[2] = 1;
		P[3] = 1;
		P[4] = 2;
		P[5] = 2;
		for (int j = 6, k = j - 5;j <= N;j++, k++) {
			P[j] = P[j - 1] + P[k];
		}

		printf("%lld\n", P[N]);
	}
	return 0;
}

---

📌 16. 스티커

백준 9465번

코드 보기

#include<stdio.h>

#define N_MAX 100000

#define Max(a,b) ((a>b)?a:b)

int sol(int score[2][N_MAX], int n) {

	int dp[2][N_MAX];	//각 행에 대한 j까지 최대 값 
	dp[0][0] = score[0][0];
	dp[1][0] = score[1][0];

	for (int j = 1;j < n;j++) {
		//score[i][j]를 넣어서 최대값을 만들 때, dp[][j-1] 또는 dp[][j-2]에 추가하는 두 경우가 있음
		dp[0][j] = score[0][j] + Max(dp[1][j - 1], dp[1][j - 2]);
		dp[1][j] = score[1][j] + Max(dp[0][j - 1], dp[0][j - 2]);
	}

	int max_sum = 0;
	for (int i = 0;i < 2;i++) {
		for (int j = 0;j < n;j++) {
			if (dp[i][j] > max_sum) max_sum = dp[i][j];
		}
	}
	return max_sum;
}
int main() {

	int T;
	scanf("%d", &T);

	for (int i = 0;i < T;i++) {
		int n;
		scanf("%d", &n);

		int score[2][N_MAX];
		for (int i = 0;i < 2;i++) {
			for (int j = 0;j < n;j++) {
				scanf("%d", &score[i][j]);
			}
		}

		int ans = sol(score, n);
		printf("%d\n", ans);
	}
	return 0;
}

---

📌 17. 퇴사 : DP 역방향

백준 14501번

DP 코드 보기

#include<stdio.h>
#include<string.h>

#define MAX (15+2)	//dp[16]을 접근하기 때문
#define Max(a,b) ((a>b)?a:b)

int main() {
	int N;
	scanf("%d", &N);

	int T[MAX] = { 0 };
	int P[MAX] = { 0 };
	for (int i = 1;i <= N;i++) {
		scanf("%d %d", &T[i], &P[i]);
	}

	int dp[MAX] = { 0 };

	for (int i = N;i >= 1;i--) {
		if (i + T[i] > N+1) {	//일하면 퇴사일 초과
			dp[i] = dp[i + 1];	//유지
		}
		else {	//일 하기
			//유지와 일 했을 때 중 큰값 넣기
			dp[i] = Max(dp[i + 1], P[i] + dp[i + T[i]]);
		}
	}

	printf("%d\n", dp[1]);

	return 0;
}

최대가 15이므로 DFS도 가능

DFS 코드 보기

#include<stdio.h>

#define MAX (15+1)

int N;
int T[MAX];
int P[MAX];
int max_profit = 0;

void dfs(int day, int profit) {

	if (day > N) {
		if (profit > max_profit) {
			max_profit = profit;
		}
		return;
	}

	if (day + T[day] - 1 <= N) {//상담 가능
		dfs(day + T[day], profit + P[day]);
	}
	dfs(day + 1, profit);	//상담 안하고 넘어가는 경우
}
int main() {

	scanf("%d", &N);
	for (int i = 1;i <= N;i++) {
		scanf("%d %d", &T[i], &P[i]);
	}

	dfs(1, 0);
	printf("%d\n", max_profit);

	return 0;
}

---

📌 18. 계단수 구하기

백준 10844번

코드 보기

#include<stdio.h>
#include<string.h>

#define MOD(a) (a % 1000000000)
#define MAX (100+1)

int main() {
	int N;
	scanf("%d", &N);

	int dp[10][MAX];	//첫수가 i이고 길이가 j인 dp
	memset(dp, 0, sizeof(dp));
	for (int i = 0;i <= 9;i++) dp[i][1] = 1;


	for (int j = 2;j <= N;j++) {
		for (int i = 0;i <= 9;i++) {	//첫수가 0이 되지 않더라도 계산에서 필요하므로
			dp[i][j] = 0;
			if (i> 0) {
				dp[i][j] += dp[i - 1][j - 1];
				dp[i][j] = MOD(dp[i][j]);
			}
			if (i < 9) {
				dp[i][j] += dp[i + 1][j - 1];
				dp[i][j] = MOD(dp[i][j]);
			}
			//printf("%d\n", dp[i][j]);
		}
	}

	int res = 0;
	for (int i = 1;i <= 9;i++) {
		res += dp[i][N];
		res = MOD(res);
	}
	printf("%d\n", res);

	return 0;
}

---

📌 19. 포도주 : 연속 3잔이 아닌 최대 3잔 구하기

백준 2156번

코드 보기

#include<stdio.h>

#define MAX (10000+1)

int max(int a, int b) {
	return (a > b) ? a : b;
}
int main() {
	int n;
	scanf("%d", &n);

	int wine[MAX];
	for (int i = 1;i <= n;i++) {
		scanf("%d", &wine[i]);
	}

	int dp[MAX];

	dp[1] = wine[1];
	dp[2] = wine[1] + wine[2];
	dp[3] = max(max(wine[1] + wine[2], wine[1] + wine[3]), wine[2] + wine[3]);
	for (int i = 4;i <= n;i++) {
		dp[i] = max(max(dp[i - 1], dp[i - 2] + wine[i]), wine[i] + wine[i - 1] + dp[i - 3]);
	}
	
	printf("%d\n", dp[n]);
	return 0;
}

📌 20. 1,2,3 더하기

백준 15988번

dp[i]를 구할 때, 마지막 숫자가 1,2,3이냐에 따라 dp[i-1], dp[i-2], dp[i-3]과 관련
점화식 : dp[i] = dp[i-1] + dp[i-2] + dp[i-3] dp,int형 오버플로우 방지

코드 보기

#include<stdio.h>

#define MOD(a) ((a)%1000000009)
#define MAX 1000000

int main() {
	int T;
	scanf("%d", &T);

	int dp[MAX + 1] = { 0 };
	dp[1] = 1;	// 1 = 1
	dp[2] = 2;	// 2 = 2 = 1+1
	dp[3] = 4;	// 3 = 3 = 2+1 = 2+1 = 1+1+1

	for (int i = 4;i <= MAX;i++) {
		dp[i] = MOD(MOD(dp[i - 1] + dp[i - 2]) + dp[i - 3]);
		//두 수 연산마다 MOD연산을 통해 int형 오버플로우를 방지
	}

	while (T--) {
		int n;
		scanf("%d", &n);
		printf("%d\n", dp[n]);
	}

	return 0;
}
/*
점화식 구하기
마지막 숫자로 1,2,3을 넣냐에 따라
1: 1
2: 2
3: 4
---
4: 7
5: 13
6: 24

dp[i] = dp[i-1] + dp[i-2] + dp[i-3] (i>=4)

*/

📌 21. 자두나무

백준 2240번

첫 코드 보기

#include<stdio.h>

#define MAX(a,b) ((a>b)?a:b)
#define TMAX 1000
#define WMAX 30

int main() {
    int T, W;
    scanf("%d %d", &T, &W);
    int drop[TMAX + 1] = { 0 };
    for (int i = 1; i <= T; i++) {
        scanf("%d", &drop[i]);
    }

    //dp[t][w][p] : t(초) w(남은 이동 횟수) p(위치) 
    int dp[TMAX + 1][WMAX + 1][2 + 1] = { 0 };

    // 초기값
    dp[1][W][1] = (drop[1] == 1) ? 1 : 0;
    dp[1][W - 1][2] = (drop[1] == 2) ? 1 : 0;

    for (int i = 2; i <= T; i++) {
        for (int j = 0; j <= W; j++) {
            for (int k = 1; k <= 2; k++) {
                //1. 이번 초 k 위치에서 얻는 사과
                int get = (drop[i] == k) ? 1 : 0;

                //2. 이동 안한거
                dp[i][j][k] = dp[i - 1][j][k] + get;

                //2. 이동 한거
                if (j < W) {
                    dp[i][j][k] = MAX(dp[i][j][k], dp[i - 1][j + 1][3 - k] + get);
                }

            }
        }
    }

    //3. T초에서의 최대값 찾기
    int ans = 0;
    for (int w = 0; w <= W; w++) {
        for (int p = 1; p <= 2; p++) {
            ans = MAX(ans, dp[T][w][p]);
        }
    }

    printf("%d\n", ans);


    return 0;
}
/*
매초마다 두개의 나무중 하나에서 열매 떨어짐
움직이는 시간 0초
자두는 T초동안 떨어짐, 최대 W번 움직이고 싶
---
#1)
7 2
2 1 1 2 2 1 1

*/

메모리 최적화 코드 보기

#include<stdio.h>

#define MAX(a,b) ((a>b)?a:b)
#define TMAX 1000
#define WMAX 30

int main() {
    int T, W;
    scanf("%d %d", &T, &W);
    int drop[TMAX + 1] = { 0 };
    for (int i = 1; i <= T; i++) {
        scanf("%d", &drop[i]);
    }

    //dp[w][p] : t(초) w(남은 이동 횟수) p(위치) 
    int dp[TMAX + 1][WMAX + 1][2 + 1] = { 0 };

    // 초기값
    dp[1][W][1] = (drop[1] == 1) ? 1 : 0;
    dp[1][W - 1][2] = (drop[1] == 2) ? 1 : 0;

    for (int i = 2; i <= T; i++) {
        for (int j = 0; j <= W; j++) {
            for (int k = 1; k <= 2; k++) {
                //1. 이번 초 k 위치에서 얻는 사과
                int get = (drop[i] == k) ? 1 : 0;

                //2. 이동 안한거
                dp[i][j][k] = dp[i - 1][j][k] + get;

                //2. 이동 한거
                if (j < W) {
                    dp[i][j][k] = MAX(dp[i][j][k], dp[i - 1][j + 1][3 - k] + get);
                }

            }
        }
    }

    //3. T초에서의 최대값 찾기
    int ans = 0;
    for (int w = 0; w <= W; w++) {
        for (int p = 1; p <= 2; p++) {
            ans = MAX(ans, dp[T][w][p]);
        }
    }

    printf("%d\n", ans);

    return 0;
}

자두 떨어지는 위치 1,2를 0,1로 변환하면 메모리 더 최적화 가능

📌 22. 극장 좌석

백준 2302번

내 코드 보기

#include<stdio.h>

#define NMAX 40

int main() {
	int N, M;
	scanf("%d%d", &N, &M);

	int max_term = 0;
	int prev_fixed = 0;
	int termArr[NMAX + 1];	// fixed로 구분한 각 term의 요소 개수

	int i = 1;
	for (i = 1;i <= M;i++) {
		int cur_fixed = 0;
		scanf("%d", &cur_fixed);

		termArr[i] = cur_fixed - prev_fixed - 1;
		if (termArr[i] > max_term) {
			max_term = termArr[i];
		}
		prev_fixed = cur_fixed;
	}
	// 마지막 term
	termArr[i] = N - prev_fixed;
	if (termArr[i] > max_term) max_term = termArr[i];

	int dp[NMAX + 1] = { 0 };
	dp[1] = 1;
	dp[2] = 2;
	for (int i = 3;i <= max_term;i++) {
		dp[i] = dp[i - 1] + dp[i - 2];
		//printf("dp[%d] : %d\n", i, dp[i]);
	}

	int mult = 1;
	for (int i = 1;i <= M + 1;i++) {
		if (termArr[i] == 0) continue;	// fixed가 1이어서 앞구간 요소 개수가 0인 경우 패스
		mult *= dp[termArr[i]];
		//printf("mult: %d | termArr[%d] : %d\n", mult, i, termArr[i]);
	}

	printf("%d\n", mult);

	return 0;
}
/*
해당 좌석의 좌,우로 자리 옮기기 가능
vip는 자기 자리에만 앉을 수 있다

#1)
123 56 89

3 * 2 * 2 = 12

1234 : 4

1234 
2134 
1324
1243
2143

*/

GPT 코드 보기

#include <stdio.h>

int dp[41] = {1, 1, 2}; // 피보나치 배열 (초기 값 설정)

int main() {
    int N, M, vip, prev = 0, result = 1;
    
    scanf("%d %d", &N, &M);
    
    // 피보나치 수열 미리 계산 (좌석 개수 최대 40이므로 가능)
    for (int i = 3; i <= N; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }

    for (int i = 0; i < M; i++) {
        scanf("%d", &vip);
        result *= dp[vip - prev - 1]; // 일반 좌석 그룹의 경우의 수 곱하기
        prev = vip;
    }
    
    result *= dp[N - prev]; // 마지막 그룹 경우의 수 반영

    printf("%d\n", result);
    
    return 0;
}

GPT코드가 좀 더 간단하고 명료함

📌 23. 오르막 수

백준 11057번

#define MOD(a) ((a)%10007) (a)에 괄호 꼭 치기!!! 결과 달라짐

코드 보기

#include<stdio.h>

#define MAX_N 1000
#define MOD(a) ((a)%10007)	//(a)에 괄호 꼭 치기!!! 결과 달라짐

int main() {
	int N;
	scanf("%d", &N);

	int dp[MAX_N + 1][10] = { 0 };	//[i][j] //i : 자리수, j : 추가할 수
	for (int i = 0;i <= 9;i++) dp[1][i] = 1;	//초기값

	for (int i = 2;i <= N;i++) {
		for (int j = 0;j <= 9;j++) {

			for (int k = 0;k <= 9;k++) {
				if (k <= j) {	//i번째 자리에 j를 추가하려면 i-1번째 자리(k)가 j보다 작을때만 가능
					dp[i][j] = MOD(dp[i][j] + dp[i - 1][k]);
				}
			}
		}
	}

	int res = 0;
	for (int i = 0;i <= 9;i++) {
		res = MOD(res + dp[N][i]);
	}
	printf("%d\n", res);

	return 0;
}
/*
오르막수
오름차순을 이루는 수(인접한 수 같아도 됨)
ex) 2234 3678 11119
자리수 N

오르막 수의 개수를 구하라
---

*/

📌 24. 삼각 그래프

백준 4883번

코드 보기

#include<stdio.h>

#define MIN(a,b) ((a)<(b)?(a):(b))

int main() {

	int T = 0;
	while (1) {
		T++;

		int N;
		scanf("%d", &N);
		if (N == 0) break;

		int min_cost = 0;
		int cost[3] = { 0, 0, 0 };
		int prev_cost[3] = { 0,0,0 };
		int first_input[3];	//첫 입력만 저장 : 첫 출발이 가운데 고정이므로 첫행 비용은 따로 계산

		//첫행
		scanf("%d %d %d\n", &first_input[0], &first_input[1], &first_input[2]);
		cost[0] = first_input[1];
		cost[1] = first_input[1];
		cost[2] = first_input[1] + first_input[2];

		//나머지행
		for (int i = 0;i < (N - 1) * 3;i++) {
			int input = 0;
			scanf("%d", &input);

			if ((i + 1) % 3 == 1) {			//3 6 ...
				prev_cost[0] = cost[0];

				cost[0] = MIN(cost[0], cost[1]);
				cost[0] += input;
			}
			else if ((i + 1) % 3 == 2) {	//4 7 ...
				prev_cost[1] = cost[1];

				cost[1] = MIN(MIN(MIN(cost[0], cost[1]), prev_cost[0]), cost[2]);
				cost[1] += input;
			}
			else if ((i + 1) % 3 == 0) {	//5 8 ...
				prev_cost[2] = cost[2];

				cost[2] = MIN(MIN(cost[1], prev_cost[1]), cost[2]);
				cost[2] += input;
			}
			//printf("====%d %d %d\n", cost[0], cost[1], cost[2]);
		}

		printf("%d. %d\n", T, cost[1]);
	}

	return 0;
}
/*
문제를 잘 살펴보면,
해당 행 계산에 필요한 값은 현재 행과 이전행 총 6개의 int형만 필요

*/

📌 25. 동전1

백준 2293번

코드 보기

#include<stdio.h>

#define MAX_N 100
#define MAX_K 10000

int main() {
    int n, k;
    scanf("%d %d", &n, &k);

    int dp[MAX_K + 1] = { 0 };
    int coin[MAX_N] = { 0 };
    for (int i = 0;i < n;i++) {
        scanf("%d", &coin[i]);
        //dp[coin[i]] = 1;
    }
 
    dp[0] = 1;  // 0을 만드는 방법 : 아무 동전도 사용 안함
    
    // 반복문의 순서가 중요
    // i금액이 되게끔 j 동전을 먼저 배치
    // 결과에 동전의 순서 고려 x : 동전 먼저, 금액 나중
    for (int j = 0;j < n;j++) { // 추가할 coin 반복
        for (int i = 1;i <= k;i++) {    //금액 반복
            if (i >= coin[j]) {
                dp[i] += dp[i - coin[j]];
                //printf("%d %d | %d\n", i, j, dp[i]);
            }
        }
    }
    /*
    // i를 만들 때 다음 자리에 1,2,5중하나인 j를 추가
    // 결과에 동전의 순서가 고려됨 : 금액 먼저, 동전 나중
    for (int i = 1;i <= k;i++) {    //금액 반복
        for (int j = 0;j < n;j++) { //추가할 coin 반복
            if (i >= coin[j]) {
                dp[i] += dp[i - coin[j]];
                //printf("%d %d | %d\n", i, j, dp[i]);
            }
        }
    }
    */
    printf("%d\n", dp[k]);
    return 0;
}
/*
동전을 적당히 사용해서 가치합이 k원이 되도록하는 경우의 수
규칙성
10 =
1+1+1+1+1+1+1+1+1+1
1+1+1+1+1+1+1+1+2
1+1+1+1+1+1+2+2
1+1+1+1+2+2+2
1+1+1+1+1+5
1+1+2+2+2+2
2+1+1+1+5
2+2+2+2+2
2+2+1+5
5+5

*/

📌 26. 내려가기

백준 2096번

코드 보기

#include<stdio.h>

#define INF (~(1<<31))
#define MAX(a,b) (((a)>(b))?(a):(b))
#define MIN(a,b) (((a)<(b))?(a):(b))

int main() {
	int N;
	scanf("%d", &N);

	int input[3] = { 0 };

	// [i][j] : i : 0,1,2 입력하는 세 수, j : 0은 이전 값, 1은 현재 값
	int max_dp[3][2] = { 0 };
	int min_dp[3][2] = { 0 };

	for (int i = 0;i < N;i++) {
		scanf("%d %d %d", &input[0], &input[1], &input[2]);

		max_dp[0][1] = MAX(max_dp[0][0], max_dp[1][0]) + input[0];
		max_dp[1][1] = MAX(MAX(max_dp[0][0], max_dp[1][0]), max_dp[2][0]) + input[1];
		max_dp[2][1] = MAX(max_dp[1][0], max_dp[2][0]) + input[2];

		min_dp[0][1] = MIN(min_dp[0][0], min_dp[1][0]) + input[0];
		min_dp[1][1] = MIN(MIN(min_dp[0][0], min_dp[1][0]), min_dp[2][0]) + input[1];
		min_dp[2][1] = MIN(min_dp[1][0], min_dp[2][0]) + input[2];


		for (int i = 0;i < 3;i++) {
			max_dp[i][0] = max_dp[i][1];
			min_dp[i][0] = min_dp[i][1];
		}

		//printf(">>%d %d %d\n", max_dp[0][1], max_dp[1][1], max_dp[2][1]);
	
	}

	int max = 0;
	int min = INF;
	for (int i = 0;i < 3;i++) {
		if (max_dp[i][1] > max) max = max_dp[i][1];
		if (min_dp[i][1] < min) min = min_dp[i][1];
	}
	printf("%d %d\n", max, min);

	return 0;
}
/*
얻을 수 있는 최대 점수와 최소 점수 구하라

첫 줄에서 시작해서 마지막 줄에서 끝

#1)
3
1 2 3
4 5 6
4 9 0

ans: 18 6
max 3 6 9 : 18
min 1 5 0 : 6

*/

📌 27. 파이프 옮기기1

백준 17070번

첫 코드(dfs) 보기

#include<stdio.h>
#include<stdbool.h>

#define MAX_MAP 16

enum Map {
	EMPTY = 0,
	WALL = 1,
};

typedef struct {
	int x;
	int y;
}Pos;

typedef struct {
	Pos head;
	Pos tail;
}Pipe;

int N;
int map[MAX_MAP][MAX_MAP];

bool visited[MAX_MAP][MAX_MAP];

int cnt = 0;
int movePipe(Pipe cur, Pipe newArr[3]) {
	int ret = 0;
	
	Pos newHead = { 0 };
	Pos newTail = (Pos){ cur.head.x, cur.head.y };

	// 가로
	if (cur.head.x == cur.tail.x) {
		newHead = (Pos){ cur.head.x, cur.head.y + 1 };
		newArr[0] = (Pipe){ newHead, newTail };

		newHead = (Pos){ cur.head.x + 1, cur.head.y + 1 };
		newArr[1] = (Pipe){ newHead,newTail };
		ret = 2;
	}
	// 세로
	else if (cur.head.y == cur.tail.y) {
		newHead = (Pos){ cur.head.x + 1, cur.head.y };
		newArr[0] = (Pipe){ newHead, newTail };

		newHead = (Pos){ cur.head.x + 1, cur.head.y + 1 };
		newArr[1] = (Pipe){ newHead,newTail };
		ret = 2;
	}
	// 대각선 아래
	else if ((cur.head.x == cur.tail.x + 1) && (cur.head.y == cur.tail.y + 1)) {
		newHead = (Pos){ cur.head.x, cur.head.y + 1 };	// 가로
		newArr[0] = (Pipe){ newHead, newTail };

		// 대각
		newHead = (Pos){ cur.head.x + 1, cur.head.y + 1 };
		newArr[1] = (Pipe){ newHead,newTail };

		newHead = (Pos){ cur.head.x + 1, cur.head.y };	// 세로
		newArr[2] = (Pipe){ newHead, newTail };

		ret = 3;
	}

	return ret;
}
void dfs(Pipe cur, Pos end) {
	
	bool endFlagHead = (cur.head.x == end.x) && (cur.head.y == end.y);
	bool endFlagTail = (cur.tail.x == end.x) && (cur.tail.y == end.y);

	if (endFlagHead || endFlagTail) {
		cnt++;
		return;
	}

	Pipe newArr[3] = { 0,0,0,0 };
	int numOfMove = movePipe(cur, newArr);	// 현재 파이프 가로, 세로면 이동 방법 : 2, 대각선이면 이동 방법 : 3
	
	for (int i = 0;i < numOfMove;i++) {
		Pos newHead = newArr[i].head;
		//printf("%d %d %d %d\n", newHead.x >= 0, newHead.x < N, newHead.y >= 0, newHead.y);

		if (newHead.x >= 0 && newHead.x < N && newHead.y >= 0 && newHead.y < N) {
			//printf("%d %d | %d\n", newArr[i].head.x, newArr[i].head.y, N);

			if (map[newHead.x][newHead.y] == WALL) continue;

			if (i == 1) {	// 대각선은 추가로 확인
				if (newHead.x >= 1 && map[newHead.x - 1][newHead.y] == WALL) continue;
				if (newHead.y >= 1 && map[newHead.x][newHead.y - 1] == WALL) continue;
			}
			dfs(newArr[i], end);
		}
	}
}
int main() {

	scanf("%d", &N);
	for (int i = 0;i < N;i++) {
		for (int j = 0;j < N;j++) {
			scanf("%d", &map[i][j]);
		}
	}

	Pipe start = { (Pos) { 0,1 }, (Pos) { 0,0 } };
	Pos end = { N - 1, N - 1 };

	dfs(start, end);

	printf("%d\n", cnt);

	return 0;
}
/*
파이프는 항상 빈칸만 차지
오른쪽, 대각선아래, 아래
회전은 45도로


*/

개선 코드(dp) 보기

#include <stdio.h>

int n, map[17][17];
int dp[17][17][3];

int main() {
    scanf("%d", &n);

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            scanf("%d", &map[i][j]);
        }
    }

    // 초기 상태 (1,2)에 가로 방향으로 파이프가 있음
    dp[1][2][0] = 1;

    // DP 수행
    for (int i = 1; i <= n; i++) {
        for (int j = 2; j <= n; j++) {
            if (map[i][j] == 1) continue; // 벽이면 이동 불가

            // 가로 → 가로 (→) 가 되는 방법
            if (j > 1) dp[i][j][0] += dp[i][j - 1][0] + dp[i][j - 1][2];

            // 세로 ↓ 세로 가 되는 방법
            if (i > 1) dp[i][j][1] += dp[i - 1][j][1] + dp[i - 1][j][2];

            // 대각선 ↘ 대각선 이 되는 방법
            if (i > 1 && j > 1) {
                if (map[i - 1][j] == 0 && map[i][j - 1] == 0) {	// 대각선은 두칸이 추가로 비어야함
                    dp[i][j][2] += dp[i - 1][j - 1][0] + dp[i - 1][j - 1][1] + dp[i - 1][j - 1][2];
                }
            }
        }
    }

    // 최종 결과: (n, n)에 도달하는 모든 방법의 합
    printf("%d\n", dp[n][n][0] + dp[n][n][1] + dp[n][n][2]);

    return 0;
}

파이프의 이동방향이 오른쪽, 아래, 오른쪽대각선아래 방향으로만 고정되어있고, 도착하는 방법의 수를 구하는 것이 문제
-> DP가 효율적, 움직인 결과의 모양[3]을 기준으로 dp 설계

###