[백준] 14722번 우유 도시 (C++)

https://www.acmicpc.net/problem/14722

 

 

이 문제는 N X M 배열이 주어지고 각 요소가 0, 1, 2로 주어졌을때 

시작 지점 (1,1) 에서 도착지점 (N, M)까지 올때 먹을 수 있는 우유의 최대 개수를 구하는 문제이다.

 

이때 갈 수 있는 방향은 오른쪽 방향과 아래 방향으로만 이동할 수 있으며

 

문제 조건에 의해서 첫번째는 무조건 딸기우유(0)을 먹어야 하며 이후에는 초코우유(1)을 먹어야 하며 그 이후 바나나우유(2)를 먹어야 하며 반복이 된다.

 

이 문제를 해결하기 위해 (1,1)에서 시작하여 오른쪽과 아래로만 이동하며 현재 상태(어떤 우유를 먹어야하는지)를 체크하여 최댓값을 출력해야하는데

 

dp(탑다운) 방식을 사용하여 해결하였다.

 

 

정답코드

 

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
#define endl "\n"

const int INF = 1e9;
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
int N;
int graph[1001][1001];
int dp[1001][1001][4];

int func(int x, int y, int status) {
    if(x >= N || y >= N) return 0;
    int &ret = dp[x][y][status];

    if(ret != -1) return ret;

    int nextmilk = status;
    int bonus = 0;

    if(graph[x][y] == status) {
        nextmilk = (status + 1) % 3;
        bonus = 1;
    }

    ret = bonus + max(func(x+1, y, nextmilk), func(x, y+1, nextmilk));

    return ret;
}

void solve() {
    cout << func(0, 0, 0);
}

void input() {
    cin >> N;

    for(int i = 0; i < N; i++) {
        for(int j = 0; j < N; j++) {
            cin >> graph[i][j];
        }
    }

    memset(dp, -1, sizeof(dp));
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    input();
    solve();
}

 

먼저 정답코드를 하나씩 뜯어보자

 

int func(int x, int y, int status) {
    if(x >= N || y >= N) return 0;
    int &ret = dp[x][y][status];

    if(ret != -1) return ret;

    int nextmilk = status;
    int bonus = 0;

    if(graph[x][y] == status) {
        nextmilk = (status + 1) % 3;
        bonus = 1;
    }

    ret = bonus + max(func(x+1, y, nextmilk), func(x, y+1, nextmilk));

    return ret;
}

 

func 함수는 x좌표, y좌표, 현재상태(어떤 우유를 먹어야하는지)를 매개변수로 받는 함수이다. 이후 x, y좌표가 N의 크기를 넘어가면 0을 리턴하였고 이미 dp 테이블에 값이 있는 경우 그 값을 리턴하도록 하였다.

 

현재 있는 좌표가 먹어야 하는 우유이면 bonus를 1을 만들어 더해주였으며 오른쪽으로 가는 것과 아래로 가는 것중 최댓값을 가져오는 로직으로 작성하였다.