[Google Kick Start] 2021 구글 킥스타트 Round A L shaped plots 풀이

 

문제

---

https://codingcompetitions.withgoogle.com/kickstart/round/0000000000436140/000000000068c509#problem

Kick Start - Google’s Coding Competitions

 

 

나의 풀이

---

본 무제는 DP를 사용하는 문제이다. test set 2의 사이즈를 보면 유추할 수 있겠지만 대략 O(R*C) 시간복잡도 내에 풀어야 통과 가능하다. 그 말은 즉, matrix의 한 위치를 한 번씩만 탐색해서 답을 찾아내야 한다는 것이다. 한 번씩만 탐색하는데 가능한 경우를 찾으려면 탐색하는 순간의 (i,j)가 L shape에서 교차점이라고 생각하고 찾으면 된다.

만약 (i,j) 위치를 기준으로 위로 6칸, 오른쪽으로 4칸을 연장시킬 수 있다고 해보자. 그러면 (위, 오른쪽) = (6,3), (4,2), (2, 4)의 3가지 경우가 가능하다. 문제의 조건에서 긴 쪽은 작은 쪽의 길이의 2배라고 하였으니, 일반화 시켜 위로 U, 오른쪽으로 R만큼 뻗어나갈 수 있다면 U가 긴 쪽인 경우는 max(min(U//2, R) - 1, 0)만큼, R이 긴 쪽인 경우는 max(min(R//2, U) - 1, 0)만큼이 가능하다. 1을 빼주고 0과 max를 취해주는 이유는 문제의 조건에서 짧은 쪽의 길이가 최소 2라고 하였기 때문에 만약 min(U//2, R)의 결과가 1이나 0이 나오는 경우를 제외해주기 위해서다.

 

코드

---

# https://codingcompetitions.withgoogle.com/kickstart/round/0000000000436140/000000000068c509#analysis
import copy
T = int(input())
for t in range(T):
    arr = []
    r,c = map(int, input().split())
    for i in range(r):
        temp = list(map(int, input().split()))
        arr.append(temp)
    U, D, L, R = copy.deepcopy(arr), copy.deepcopy(arr), copy.deepcopy(arr), copy.deepcopy(arr)
    for i in range(1, r):
        for j in range(c):
            if arr[i][j] == 1:
                U[i][j] += U[i-1][j]
    for i in range(r-2, -1, -1):
        for j in range(c):
            if arr[i][j] == 1:
                D[i][j] += D[i+1][j]
    for i in range(r):
        for j in range(1,c):
            if arr[i][j] == 1:
                L[i][j] += L[i][j-1]
    for i in range(r):
        for j in range(c-2, -1, -1):
            if arr[i][j] == 1:
                R[i][j] += R[i][j+1]
    ans = 0
    for i in range(r):
        for j in range(c):
            ans += max(min(U[i][j]//2, R[i][j])-1, 0)
            ans += max(min(U[i][j]//2, L[i][j])-1, 0)
            ans += max(min(D[i][j]//2, R[i][j])-1, 0)
            ans += max(min(D[i][j]//2, L[i][j])-1, 0)
            ans += max(min(R[i][j]//2, D[i][j])-1, 0)
            ans += max(min(R[i][j]//2, U[i][j])-1, 0)
            ans += max(min(L[i][j]//2, D[i][j])-1, 0)
            ans += max(min(L[i][j]//2, U[i][j])-1, 0)
    print(f"Case #{t+1}: " + str(ans))