[Python] 백준 33965번: 주사위 피라미드

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

 

 

 

 

[풀이]

일정한 규칙을 찾고자 노력했다.

 

주사위가 한 면이 가려진 경우, 최소 값은 6이 가려진 (1+2+3+4+5) = 15, 최대 값은 1이 가려진 (2+3+4+5+6) = 20

주사위가 두 면이 가려진 경우, 최소 값은 (1+2+3+4) = 11, 최대 값은 (3+4+5+6) = 18 일 것이다.

이렇게 한 면이 가려진 경우부터, 여섯 면이 모두 가려진 경우에 대해 계산을 한다.

 

주사위의 구조는, 1과 6, 2와 5, 3과 4라는 숫자가 서로 마주보게 설계되어 있다.

그리고 한 면이 가려지는 경우는 6가지이지만, 결국 회전하면 되기 때문에 최소 값과 최대 값은 항상 일정하게 구할 수 있다.

두 면이 가려지는 경우는 역시 경우의 수는 많지만, 모든 경우의 수 모두 회전하면 동일하게 구할 수 있을 것이다.

 

이런 공식을 도출하여, 피라미드의 층이 N개일 때에 대해 하나 씩 구해보았다.

 

N이 1인 경우, 바닥 면이 가려진 경우 하나이기 때문에, 최소 값은 15, 최대 값은 20이므로, 합계 35

N이 2인 경우, 맨 위층 DP[1]에 더해, 아래 층인 양 끝 4개 면이 보이는 두 개의 주사위와 가운데에 있는 두 개 면이 드러난 한 개의 주사위가 있을 것이다.

 

이렇게 N이 4개인 경우까지 구하다 보면 하나의 규칙을 찾을 수 있다.

참고로, dice[i]에 대해서는 i개의 면이 드러난다고 가정한다.

 

dice[5]

+ dice[4] * 2 * (n - 1)

+ dice[2] * (n - 1)

+ dice[1] * 2 * ((n - 2) * (n - 1) // 2)

+ dice[3] * ((n - 2) * (n - 1) // 2)

 

라는 점화식을 하나 얻을 수 있다.

이 공식을 통해 최솟 값과 최대 값에 대해 N을 대입하여 두 번 연산 후 해당 값을 더해서 출력하였다.

 

====

 

이와 별개로, 조금 더 수식을 단순화 시킬 수도 있다.

 

N이 1일 때는, 35

N이 2일 때는, 105

N이 3일 때는, 210

N이 4일 때는, 350

...

 

이렇게 결과 값에 대한 수를 보면 일정한 규칙이 나오는데,

해당 규칙을 토대로 하나의 공식을 도출해 낼 수 있을 것이다.

 

35 * (n * (n + 1)) // 2

 

이렇게 O(1)의 속도로 결과 값을 구할 수 있다,

 

Special Thanks to. sk14cj

:)

 

 

 

[코드]

n = int(input())

dice = [[0, 1, 3, 6, 10, 15], [0, 6, 11, 15, 18, 20]]
result = 0

for i in range(2):
    result += (
    dice[i][5]
    + dice[i][4] * (2 * (n - 1))
    + dice[i][2] * (n - 1)
    + dice[i][1] * 2 * ((n - 2) * (n - 1) // 2)
    + dice[i][3] * ((n - 2) * (n - 1) // 2)
    )

print(result)

 

 

 

[시간복잡도]

O(1)