1. 오늘의 문제
오늘 문제는 보자마자 귀찮음이 몰려왔다.
일단 주사위가 있는데 주사위가 마주보는 면의 합이 7이 아니었고, 전개도가 따로 주어졌다.
그럼 전개도에 맞춰서 서로 마주보는 면, 그리고 사이드의 숫자 인덱스들을 딕셔너리로 만들어야 겠다는 생각이 들었다.
일단 풀어보기로 했다.
문제
천수는 여러 종류의 주사위를 가지고 쌓기 놀이를 하고 있다. 주사위의 모양은 모두 크기가 같은 정육면체이며 각 면에는 1부터 6까지의 숫자가 하나씩 적혀있다. 그러나 보통 주사위처럼 마주 보는 면에 적혀진 숫자의 합이 반드시 7이 되는 것은 아니다.
주사위 쌓기 놀이는 아래에서부터 1번 주사위, 2번 주사위, 3번 주사위, … 의 순서로 쌓는 것이다. 쌓을 때 다음과 같은 규칙을 지켜야 한다: 서로 붙어 있는 두 개의 주사위에서 아래에 있는 주사위의 윗면에 적혀있는 숫자는 위에 있는 주사위의 아랫면에 적혀있는 숫자와 같아야 한다. 다시 말해서, 1번 주사위 윗면의 숫자는 2번 주사위 아랫면의 숫자와 같고, 2번 주사위 윗면의 숫자는 3번 주사위 아랫면의 숫자와 같아야 한다. 단, 1번 주사위는 마음대로 놓을 수 있다.
이렇게 쌓아 놓으면 긴 사각 기둥이 된다. 이 사각 기둥에는 4개의 긴 옆면이 있다. 이 4개의 옆면 중에서 어느 한 면의 숫자의 합이 최대가 되도록 주사위를 쌓고자 한다. 이렇게 하기 위하여 각 주사위를 위 아래를 고정한 채 옆으로 90도, 180도, 또는 270도 돌릴 수 있다. 한 옆면의 숫자의 합의 최댓값을 구하는 프로그램을 작성하시오.
입력
첫줄에는 주사위의 개수가 입력된다. 그 다음 줄부터는 한 줄에 하나씩 주사위의 종류가 1번 주사위부터 주사위 번호 순서대로 입력된다. 주사위의 종류는 각 면에 적혀진 숫자가 그림1에 있는 주사위의 전개도에서 A, B, C, D, E, F 의 순서로 입력된다. 입력되는 숫자 사이에는 빈 칸이 하나씩 있다. 주사위의 개수는 10,000개 이하이며 종류가 같은 주사위도 있을 수 있다.
2. 브루트포스 알고리즘
알고보니 이 문제는 원래 이렇게 푸는 문제였다.
브루트포스 알고리즘이란 brute(무식한, 짐승) + force(힘) = brute-force(난폭함, 무식한 힘) 에서 나온 말이다.
그러니 무차별적으로 대입해서 답이 나오도록 만들면 됨.
다르게 표현하면 단순 노가다이다.
3. 코드
from sys import stdin
# 다이스의 하부 면이 주어질 때
# 상부, 사이드의 인덱스를 딕셔너리로 만듦
dct = {
0 : (5 ,[1, 2, 3, 4]),
1 : (3 ,[0, 2, 4, 5]),
2 : (4 ,[0, 1, 3, 5]),
3 : (1 ,[0, 2, 4, 5]),
4 : (2 ,[0, 1, 3, 5]),
5 : (0 ,[1, 2, 3, 4])
}
# 주사위의 개수와 숫자들을 받음
put = stdin.readline
numOfDice = int(put())
diceFaces = []
for _ in range(numOfDice):
diceFace = list(map(int, put().split()))
diceFaces.append(diceFace)
# 경우의 수에 따른 총합을 리스트로 만듦
# 첫번째 주사위를 선정함
totals = []
firstDice = diceFaces[0]
# 첫번째 주사위에서 제일 아랫면에 따라 for문을 돈다.
# 하부 인덱스에 따른 상부 인덱스를 구하고 다음 숫자를 추정한다.
# 그리고 옆면에서 최댓값을 구해 total에 더해준다.
for i, firstNum in enumerate(firstDice):
total = 0
nextNumIndex, sideNumsIndexs = dct[i]
maxNum = 0
for sideNumIndex in sideNumsIndexs:
if firstDice[sideNumIndex] > maxNum:
maxNum = firstDice[sideNumIndex]
total += maxNum
nextNum = firstDice[nextNumIndex]
# 마찬가지의 방법으로 다음 숫자를 추정하고 옆면의 숫자를 구한다.
# 최댓값을 구해 total에 더해준다.
for dice in diceFaces[1:]:
bottomNum = nextNum
bottomIndex = dice.index(bottomNum)
topIndex, sideNumIndexs = dct[bottomIndex]
topNum = dice[topIndex]
maxNum = 0
for sideNumIndex in sideNumIndexs:
if dice[sideNumIndex] > maxNum:
maxNum = dice[sideNumIndex]
total += maxNum
nextNum = topNum
totals.append(total)
result = max(totals)
print(result)
4. 느낀점
무식하게 푸는것도 일종의 알고리즘이란는 것이 신박하게 다가왔다.
최근에는 문제 하나를 풀고 TIL을 쓰는데 까지 걸리는 시간이 1시간도 걸리지 않는 것 같다.
문제를 푸는 속도도 조금 빨라지고, 유형도 익숙해졌다.
습관의 힘이란 무서운 것이다.
