[백준] 14722번 우유 도시 c++

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

14722번: 우유 도시

 

문제

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

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

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 방식으로 접근했다.

#include <iostream>
#include <queue>
#include <algorithm>
#define VMAX 1000

using namespace std;

int n;
int b[VMAX][VMAX];
int result=0;
int w[VMAX][VMAX]={0}; // mem 배열

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

void bfs(){
    queue<pair<pair<int,int>,pair<int, int>>> q;

    if(b[0][0]==0) w[0][0]=1;
    q.push({{0,0},{w[0][0], w[0][0]}});

    while(!q.empty()){
        int x = q.front().first.first;
        int y = q.front().first.second;
        int c = q.front().second.first;
        int next = q.front().second.second;
        q.pop();
        if(x==n-1 && y==n-1){
            result = max(result, c);
        }
        for(int i=0; i<2; i++){
            int nx = x + dx[i];
            int ny = y + dy[i];
            if(nx < n && ny < n && w[nx][ny] < c){
                if(next == b[nx][ny]){
                    next++;
                    c++;
                    if(next==3) next=0;
                }
                w[nx][ny] = c;
                q.push({{nx,ny}, {c, next}});
            }
        }
    }
    return ;
}

int main()
{
    cin >> n;
    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            scanf("%d", &b[i][j]);
        }
    }
    bfs();
    
    cout << result;
    
    return 0;
}

바로 시간초과가 났다.

n의 최대값이 1000이라 당연한 결과였다.

바로 DP로 접근해야겠다는 판단이 들었다.

 

먼저 현재칸의 우유를 마실 수 있는지 여부를 판단하여 위쪽에서 내려오는 것과 왼쪽에서 오는 것 중 어느쪽이 이득인지 확인한다.

그 후 이득이 방향으로 우유사실 수 있는지 여부를 통해 mem을 채워나간다.

#include <iostream>
#include <queue>
#include <algorithm>
#include <vector>
#define VMAX 1000
#define INF 987654321

using namespace std;

int findnext(int next){
  next++;
  if(next==3) next=0;
  return next;
}

int main(){
  int n;
  int b[VMAX][VMAX];
  int mem[VMAX][VMAX];
  int v[VMAX][VMAX]={0};
  cin >> n;
  for(int i=0; i<n; i++){
    for(int j=0; j<n; j++){
      scanf("%d", &b[i][j]);
    }
  }
  if(b[0][0]==0){
    mem[0][0]=1;
    v[0][0]=1;
  }else{
    mem[0][0]=0;
    v[0][0]=0;
  }

  for(int i=1; i<n; i++){
    int next = v[0][i-1]; // 이번차례에 마실 수 있는 우유 종류 구하기

    if(next==b[0][i]){
      mem[0][i] = mem[0][i-1]+1;
      v[0][i]=findnext(next);
    }else{
      mem[0][i] = mem[0][i-1];
      v[0][i] = next;
    }
  }

  for(int i=1; i<n; i++){
    int next = v[i-1][0];// 이번차례에 마실 수 있는 우유 종류 구하기
        
    if(next==b[i][0]){
      mem[i][0] = mem[i-1][0]+1;
      v[i][0]=findnext(next);
    }else{
      mem[i][0] = mem[i-1][0];
      v[i][0]=next;
    }
  }

  for(int i=1; i<n; i++){
    for(int j=1; j<n; j++){
      // 이번차례에 마실 수 있는 우유 종류 구하기 - 각 위,왼쪽에 대해서
      int next_top = v[i-1][j];
      int next_left = v[i][j-1];

      int top, left;
      if(b[i][j] == next_top){
        top = mem[i-1][j] + 1;
      }else{
        top = mem[i-1][j];
      }
      if(b[i][j] == next_left){
        left = mem[i][j-1] + 1;
      }else{
        left = mem[i][j-1];
      }

      if(top > left){ // top 기준으로 구하기
        mem[i][j] = top;
        if(next_top==b[i][j]){
          v[i][j]=findnext(next_top);
        }else{
          v[i][j]=next_top;
        }
      }else{ // left 기준으로 구하기 어차피 우유 number를 고려한 상태이기 때문에 상관없다.
        mem[i][j] = left;
        if(next_left==b[i][j]){
          v[i][j]=findnext(next_left);
        }else{
          v[i][j]=next_left;
        }
      }

    }
  }
  cout << mem[n-1][n-1];
  
  return 0;
}

느낀점

- DP의 위력을 실감했다.

- 점화식을 좀더 깔끔하게 세워서 mem 배열하나로 접근해 다이렉트로 풀지는 못해서 아쉽다.