보물창고 블로그

백준 알고리즘 14500번 테트로미노 풀이 with Python 본문

알고리즘 풀이/백준 알고리즘

백준 알고리즘 14500번 테트로미노 풀이 with Python

홋 메 2020. 2. 25. 17:38
728x90

문제 링크: https://www.acmicpc.net/problem/14500

 

14500번: 테트로미노

폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변끼리 연결되어 있어야 한다. 즉, 꼭짓점과 꼭짓점만 맞닿아 있으면 안 된다. 정사각형 4개를 이어 붙인 폴리오미노는 테트로미노라고 하며, 다음과 같은 5가지가 있다. 아름이는 크기가 N×M인 종이 위에 테트로미노 하나를 놓으려고 한다. 종이는 1×1 크기의 칸으로 나누

www.acmicpc.net

문제는 아래와 같습니다. 

14500번 테트로미노

테트로미노가 가능한 19가지의 모양에 대해 체크하였다. 나의 풀이는 다음과 같다.

def check(i, j, map2, n, m):
    sub = 0
    # case1
    if i + 3 < n:
        sub2 = 0
        for p in range(4):
            sub2 += map2[i + p][j]
        sub = sub2
    if j + 3 < m:
        sub2 = 0
        for p in range(4):
            sub2 += map2[i][j + p]
        if sub < sub2:
            sub = sub2
    if i + 1 < n and j + 1 < m:
        sub2 = map2[i][j] + map2[i][j + 1] + map2[i + 1][j] + map2[i + 1][j + 1]
        if sub < sub2:
            sub = sub2
    if i + 2 < n and j + 1 < m:
        sub2 = map2[i][j] + map2[i + 1][j] + map2[i + 2][j] + map2[i + 2][j + 1]
        if sub < sub2:
            sub = sub2
    if i + 2 < n and j > 0:
        sub2 = map2[i][j] + map2[i + 1][j] + map2[i + 2][j] + map2[i + 2][j - 1]
        if sub < sub2:
            sub = sub2
    if i + 2 < n and j + 1 < m:
        sub2 = map2[i][j] + map2[i + 1][j] + map2[i + 1][j + 1] + map2[i + 2][j + 1]
        sub3 = map2[i][j] + map2[i][j + 1] + map2[i + 1][j] + map2[i + 2][j]
        sub4 = map2[i][j] + map2[i][j + 1] + map2[i + 1][j + 1] + map2[i + 2][j + 1]
        sub5 = map2[i][j] + map2[i + 1][j] + map2[i + 2][j] + map2[i + 1][j + 1]
        s = max(sub2, sub3, sub4, sub5)
        if s > sub:
            sub = s
    if i + 2 < n and j > 0:
        sub2 = map2[i][j] + map2[i + 1][j] + map2[i + 1][j - 1] + map2[i + 2][j - 1]
        if sub < sub2:
            sub = sub2
    if i + 1 < n and j - 2 > -1:
        sub2 = map2[i][j] + map2[i][j - 1] + map2[i + 1][j - 1] + map2[i + 1][j - 2]
        sub3 = map2[i][j] + map2[i + 1][j] + map2[i + 1][j - 1] + map2[i + 1][j - 2]
        s = max(sub2, sub3)
        if sub < s:
            sub = s
    if i + 1 < n and j + 2 < m:
        sub2 = map2[i][j] + map2[i][j + 1] + map2[i + 1][j + 1] + map2[i + 1][j + 2]
        if sub < sub2:
            sub = sub2
    if i + 1 < n and j + 2 < m:
        sub1 = map2[i][j] + map2[i][j + 1] + map2[i][j + 2] + map2[i + 1][j]
        sub2 = map2[i][j] + map2[i][j + 1] + map2[i][j + 2] + map2[i + 1][j + 2]
        sub3 = map2[i][j] + map2[i + 1][j] + map2[i + 1][j + 1] + map2[i + 1][j + 2]
        s = max(sub1, sub2, sub3)
        if s > sub:
            sub = s
    if i + 2 < n and j > 0:
        sub2 = map2[i][j] + map2[i + 1][j] + map2[i + 1][j - 1] + map2[i + 2][j]
        if sub < sub2:
            sub = sub2
    if i > 0 and j + 2 < m:
        sub2 = map2[i][j] + map2[i - 1][j + 1] + map2[i][j + 1] + map2[i][j + 2]
        if sub < sub2:
            sub = sub2
    if i + 1 < n and j + 2 < m:
        sub2 = map2[i][j] + map2[i][j + 1] + map2[i + 1][j + 1] + map2[i][j + 2]
        if sub < sub2:
            sub = sub2
    return sub


n, m = map(int, input().split())
answer = 0
map1 = [list(map(int, input().split())) for _ in range(n)]
for i in range(n):
    for j in range(m):
        ans = check(i, j, map1, n, m)
        if answer < ans:
            answer = ans
print(answer)
저작자표시 비영리 변경금지

'알고리즘 풀이 > 백준 알고리즘' 카테고리의 다른 글

백준 알고리즘 3190번 뱀 풀이 With Python  (0) 2020.03.09
백준 알고리즘 14888번 연산자 끼워넣기 풀이 with Python  (0) 2020.02.25
백준 알고리즘 3055번 탈출 풀이 with Python  (0) 2020.02.23
백준 알고리즘 15685번 드래곤 커브 풀이 with Python  (0) 2020.02.21
백준 알고리즘 12100번 2048 풀이 with Python  (0) 2020.02.01
'알고리즘 풀이/백준 알고리즘' Related Articles more
Comments