[Python] BOJ(백준) 2818 숙제하기 싫을 때

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

 

수학, 도형 감각이 약간 필요한 구현 문제다.

n X m 배열을 1, 1부터 n, m까지 주사위가 ㄹ자로 모든 면을 굴러간다.

이 때 모든 칸에서의 윗 면의 합을 구하는 문제다.

시작은 윗 면 1, 앞 면 2, 오른쪽 면 3이다. 일반 주사위와 마찬가지로 마주보는 면의 합은 7이다.

 

굴러가는 걸 하나하나 구현하는 방법이 가장 먼저 떠올랐으나

입력 범위가 n ,m < 100000 이므로 패스했다.

노가다 구현 방법도 떠오르지 않았다... 경우의 수가 너무 많아보였다.

 

그래서 생각한 건 가로의 길이가 4n + 0, 4n + 1, 4n + 2, 4n + 3인 경우로 나누어 생각했다.

사실 1, 2, 3, 4만 생각해보고 그 후로는 계속 반복될 것이라고 생각했다.

몇 줄을 내려가야 처음 상태로 돌아오는지 나름 규칙도 파악했는데 애초에 가정이 틀렸었다.

1, 2, 3, 4, 5, 6, 7, 8 ... 모든 경우의 수가 다르다. (m이 1일 때, 5일 때, 같은 규칙일 것이라고 생각했다.)

부끄럽지만 아래는 열심히 따져본 흔적이다... 공책 한 장 찢어서 주사위도 만들었다...

 

각각의 누적합을 구해 코드도 짰었지만 처참히 실패했다.

n, m = map(int, input().split())
nm = n * m

lst = [[171, 1, 5, 11, 14, 19, 25, 27, 28, 
        32, 34, 37, 42, 48, 51, 52, 56, 
        58, 59, 64, 70, 73, 78, 82, 84,
        85, 89, 95, 98, 103, 109, 111, 112,
        116, 121, 124, 129, 135, 138, 139, 143,
        145, 146, 151, 157, 160, 165, 169],
        [14, 1, 6, 12],
        [42, 1, 5, 10, 11, 14, 19, 25, 28, 30, 36, 40],
        [22, 1, 5, 11, 16, 20]]

k = m % 4
t = nm // len(lst[k])
print(t, k)
res = t * lst[k][0]
print(res)
res += lst[k][nm % len(lst[k])]

print(res)

 

하루 쉬고 다음날 생각해봤다.

주사위가 움직이는 방향은 세 개. 오른쪽, 아래, 왼쪽 세 개가 반복된다.

주사위는 옆으로 4번 굴러가면 제자리가 된다.

마주보는 두 면의 합은 7이고, 위 1, 앞 2, 오른쪽 3이다.

 

이 점을 이용해서 4x 만큼 돌면 제자리이기 떄문에 m % 4만큼 가는 것만 고려해주면 된다.

4x 만큼 돌아서 제자리로 오는 경우는 항상 14이다. (마주보는 면의 합이 7이기 때문)

각 방향으로 움직이는 함수 세 개를 만들고, 전역변수 top, front, right를 이용해 주사위의 현재 상태를 저장했다.

그리고 전 날 하나하나 따져본 데이터를 이용해 4가지 경우의 수에 따라 원점으로 돌아오는 줄 수를 이용했다.

이 방법으로 반복 작업을 최대한 줄여, 가로로 이동하는 것과 같이 마지막 일부만 계산하면 된다.

 

14 * m1 + roll_right()

semi + total * n1

이 부분이 중요한 코드다.

n, m = map(int, input().split())
m -= 1
m1 = m // 4
m2 = (m + 1) % 4

top = 1
front = 2
right = 3

def roll_right():   
    global top, front, right
    remain = top
    for i in range(m % 4):
        t = right
        right = top
        top = 7 - t
        remain += top
    return remain

def roll_left():    
    global top, front, right
    remain = top
    for i in range(m % 4):
        t = top
        top = right
        right = 7 - t
        remain += top
        
    return remain
    
def roll_down():
    global top, front, right
    t = front
    front = top
    top = 7 - t

arr = [12, 4, 6, 2]

total = 0
for i in range(arr[m2] // 2):
    total += 14 * m1 + roll_right()
    roll_down()
    total += 14 * m1 + roll_left()
    roll_down()
    
n1 = n // arr[m2]
n2 = n % arr[m2]

semi = 0
for i in range(n2):
    if i % 2 == 0:
        semi += 14 * m1 + roll_right()
    else:
        semi += 14 * m1 + roll_left()
    roll_down();
print(semi + total * n1)

 

파이썬 풀이 중에 가장 빠른 시간으로 해결했다. 뿌-듯

구현 문제를 접하면 노가다가 가장 먼저 떠오르지만 최적화에 대해 가장 많이 생각하게 되는 것 같다.

 

생각도 많이 해보고 나름 머리 안에서는 여러가지 그림이 그려지는데 텍스트로만 표현하긴 아직 어렵다.