[BOJ][🟡4][백준#14722] 우유 도시

문제 출처

BAEKJOON Online Judge #14722

문제

영학이는 딸기우유, 초코우유, 바나나우유를 좋아한다. 입맛이 매우 까다로운 영학이는 자신만의 우유를 마시는 규칙이 있다. 

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

저번 축제에서 수많은 우유를 마셨지만 더욱 우유에 갈증을 느낀 영학이는 우유 여행을 떠났다. 맛있는 우유를 찾아 떠난 영학이는 수많은 우유 가게로 둘러 쌓인 어느 도시에 도착했다. 이 도시는 정사각형 형태의 2차원 격자 모양으로 남북으로 N개, 동서로 N개, 총 N*N개의 우유 가게들이 있다. 영학이는 도시의 서북쪽 끝 (1, 1)에서 출발해서 동남쪽 아래 (N, N)까지 까지 가면서 우유를 사 마신다.  각각의 우유 가게는 딸기, 초코, 바나나 중 한 종류의 우유만을 취급한다. 각각의 우유 가게 앞에서, 영학이는 우유를 사 마시거나, 사 마시지 않는다. So cooooool~한 영학이는 오직 동쪽 또는 남쪽으로만 움직이기 때문에 한 번 지나친 우유 가게에는 다시 가지 않는다. 영학이가 마실 수 있는 우유의 최대 개수를 구하여라.

입력

첫 번째 줄에는 우유 도시의 영역 크기 N이 주어진다. (1 ≤ N ≤ 1000) 두 번째 줄부터 N+1 번째 줄까지 우유 도시의 정보가 주어진다. 0은 딸기우유만을 파는 가게, 1은 초코우유만을 파는 가게, 2는 바나나우유만을 파는 가게를 뜻하며, 0, 1, 2 외의 정수는 주어지지 않는다.

출력

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

예제

예제 1

입력

4
0 1 2 2
1 1 1 1
2 2 2 2
0 0 1 0

출력

5

예제 2

입력

5
0 1 0 0 0
1 2 1 1 1
2 0 1 2 0
0 0 0 0 1
1 1 1 1 2

출력

9

My Sol

import sys
input = sys.stdin.readline

N = int(input())
mat = [list(map(int, input().split())) for _ in range(N)]
dp = [[[0, -1] for _ in range(N+1)] for _ in range(N+1)]

for i in range(1, N+1):
    for j in range(1, N+1):
        left, up = dp[i][j-1], dp[i-1][j]
        left_check = (left[1]+1)%3 == mat[i-1][j-1]
        up_check = (up[1]+1)%3 == mat[i-1][j-1]

        left_score = left[0] + left_check
        up_score = up[0] + up_check
        if left_score > up_score:
            dp[i][j][0] = left_score
            dp[i][j][1] = mat[i-1][j-1] if left_check else left[1]

        else:
            dp[i][j][0] = up_score
            dp[i][j][1] = mat[i-1][j-1] if up_check else up[1]

print(dp[N][N][0])

DP를 이용하는 문제였다. 조금 특이했던 점은, 기준이 되는 위의 칸과 왼쪽 칸의 우유 정보 중 채택된 것을 저장해야 했기 때문에 3차원 배열을 사용했다.

접근은 다음과 같다.

1. dp 배열을 초기화해 만들어준다.
2. dp 위쪽과 왼쪽의 칸들에서 각각 우유 정보(각 칸[1])를 확인해 지금 위치하는 칸과 연결이 되는지 확인한다.
3. 연결이 된다면 누적 우유(각 칸[0])에 1을 더해준다.
4. 이렇게 누적 여부까지 확인한 왼쪽 칸과 위의 칸의 누적 우유를 비교해 더 큰 쪽을 채택한다.
5. 이때 채택된 칸에 이미 존재하던 우유 정보와 현재 칸의 우유 정보가 연결된다면 현재 칸의 우유 정보를, 아니라면 채택된 칸의 우유정보를 현재 칸의 우유정보에 저장한다.

dp 배열은 (N+1) x (N+1)의 크기로 정의하며, dp(1,1)에서 위쪽, 왼쪽 값을 조회하며 시작하기 때문에 range(1, N+1)로 순회한다.

구조가 복잡해 실수하는 것을 방지하기 위해 변수로 저장해가며 추가해 넣어주었다.

결과

맞았습니다!!

모범답안

출처

n=int(input())
m=[list(map(int,input().split())) for _ in range(n)]
d=[[0]*(n+1) for _ in range(n+1)]
for i in range(1,n+1):
    for j in range(1,n+1):
        d[i][j]=max(d[i-1][j],d[i][j-1])
        if d[i][j]%3==m[i-1][j-1]:d[i][j]+=1
print(d[-1][-1])

내 풀이에 비해 연산시간은 55%, 메모리 사용은 40%, 코드 길이는 30% 정도 되는 코드가 있어서 분석해보려 한다.

이 분은 우유 정보를 저장하지 않고 2차원 dp 배열을 만들어 사용했으며, 우유 정보는 현재까지의 누적 우유를 3으로 나눈 나머지와 같은 것을 이용했다… 난 왜 이 생각을 못 했지..

왼쪽, 위쪽의 dp 값 중 더 큰 값을 현재 칸에 넣고, 이를 3으로 나눈 나머지가 현재 칸의 우유 정보와 같다면 하나 더 늘려주는 방식인 것이다. 똑똑한 풀이였다.