[BOJ] 우유 도시 14722번 C++

 

문제

영학이는 딸기우유, 초코우유, 바나나우유를 좋아한다.

입맛이 매우 까다로운 영학이는 자신만의 우유를 마시는 규칙이 있다. 

1. 맨 처음에는 딸기우유를 한 팩 마신다.
2. 딸기우유를 한 팩 마신 후에는 초코우유를 한 팩 마신다.
3. 초코우유를 한 팩 마신 후에는 바나나우유를 한 팩 마신다.
4. 바나나우유를 한 팩 마신 후에는 딸기우유를 한 팩 마신다. 

저번 축제에서 수많은 우유를 마셨지만 더욱 우유에 갈증을 느낀 영학이는 우유 여행을 떠났다.

맛있는 우유를 찾아 떠난 영학이는 수많은 우유 가게로 둘러 쌓인 어느 도시에 도착했다.

이 도시는 정사각형 형태의 2차원 격자 모양으로 남북으로 N개, 동서로 N개, 총 N*N개의 우유 가게들이 있다.

영학이는 도시의 서북쪽 끝 (1, 1)에서 출발해서 동남쪽 아래 (N, N)까지 까지 가면서 우유를 사 마신다. 

각각의 우유 가게는 딸기, 초코, 바나나 중 한 종류의 우유만을 취급한다.

각각의 우유 가게 앞에서, 영학이는 우유를 사 마시거나, 사 마시지 않는다.

So cooooool~한 영학이는 오직 동쪽 또는 남쪽으로만 움직이기 때문에 한 번 지나친 우유 가게에는 다시 가지 않는다.

영학이가 마실 수 있는 우유의 최대 개수를 구하여라.

입력

첫 번째 줄에는 우유 도시의 영역 크기 N이 주어진다. (1 ≤ N ≤ 1000)

두 번째 줄부터 N+1 번째 줄까지 우유 도시의 정보가 주어진다.

0은 딸기우유만을 파는 가게, 1은 초코우유만을 파는 가게, 2는 바나나우유만을 파는 가게를 뜻하며, 0, 1, 2 외의 정수는 주어지지 않는다.

출력

 

영학이가 마실 수 있는 우유의 최대 개수를 출력하시오.

 

접근 방식

 

처음에는 BFS로 풀려고 했으나.. 메모리 초과가 발생하고 말았다.

따라서 DP를 이용해 다시 접근하려고 했다

영학이는 동쪽, 남쪽으로만 이동가능하기 때문에

dp[i-1][j], dp[i][j-1] 중에 더 큰 값을 선택하고

만약 마실 수 있는 우유라면 그 값에서 +1을, 아니라면 해당 값을 가지면 된다

이때 마실수 있는 우유인지 확인하는 방법은 3을 나눈 나머지로 간단하게 확인할 수 있다!!

 

 

코드

#include<bits/stdc++.h>
using namespace std;

int mat[1001][1001], dp[1001][1001];
int main() {
    int N; cin>>N;
    for(int i=1; i<=N; i++) {
        for(int j=1; j<=N; j++) {
            cin>>mat[i][j];
        }
    }

    for(int i=1; i<=N; i++) fill(dp[i], dp[i]+N+1, -1);
    dp[1][1] = mat[1][1] == 0 ? 1 : 0;

    for(int i=1; i<=N; i++) {
        for(int j=1; j<=N; j++) {
            if(i == 1 && j == 1) continue;

            int MAX = max(dp[i-1][j], dp[i][j-1]);

            if(mat[i][j] == (MAX % 3)) dp[i][j] = MAX+1;
            else dp[i][j] = MAX;
        }
    }
    
    cout<<dp[N][N];
}