| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1.08 초 (추가 시간 없음) | 1024 MB | 147 | 52 | 9 | 31.034% |
큐브를 하면 머리가 좋아진다는데, 실제로 큐브를 맞춰 보신 분들은 공식만 잔뜩 외우고 연습만 열심히 해서 큐브를 어떻게든 더 빨리 맞추려는 스피드큐빙 커뮤니티에 어쩌면 실망하셨을지도 모르겠습니다. 여러분들을 위해 333 최소 회전 풀이 분야를 소개드립니다.
333 최소 회전 풀이(333 Fewest Moves Solution)는 333 큐브를 최소한의 이동(move)을 사용해서 맞추는 풀이를 찾는 분야입니다. 다양한 상황을 만날 수 있고, 정말로 머리를 써야 하는 분야입니다. 예를 들어, 이 분야에서 상황에 맞는 공식을 창조하는 것은 기본 중의 기본입니다! 이 분야도 공식 대회가 열립니다. 공식 대회의 규칙은 이곳에서 보실 수 있으며, 별도로 명시되지 않은 경우 이 문제 역시 이 규칙을 따릅니다. 노트 란에 번역본 및 바뀐 규칙을 표시해 두었습니다.
키파는 컴퓨터가 333 최소 회전에 도전(Fewest Moves Challenge)하는 것은 딥 러닝의 시대에 매우 적합하다고 판단했고, 이에 맞는 규칙을 만들기 시작했습니다.
우선 컴퓨터는 연산을 1초에 1억 번 할 수 있다는 암묵의 규칙을 떠올렸습니다. 사람이 1초에 한 번 연산을 할 수 있는 건 아니지만, 1초에 한 번 연산할 수 있다고 가정하고 36억 μs에 한 개의 큐브의 해법을 얻는다면, 컴퓨터는 36μs에 한 개의 큐브의 해법을 얻어야 합니다. 36μs는 너무 작은 시간이므로 대신 3만 개의 큐브를 1.08초에 해결하는 것으로 바꾸었습니다.
다음으로 사람은 큐브의 상태를 보고 섞기 수열을 얻어낼 수 없기 때문에, 섞기 수열을 제공하고 대신 풀이가 섞기 수열과 관련이 있으면 안 된다는 조항을 넣어서 해결합니다. 섞기 수열이 제공되기 때문에 NISS 등의 방법을 사용할 수 있습니다. 컴퓨터는 큐브를 평범한 해법으로 맞춘 다음 섞기 수열을 만들어낼 수 있으므로, 섞기 수열이 필요 없습니다. 대신 큐브의 상태를 직접 주는 것으로 바꾸었습니다.
이런 귀찮은 일을 하고 있자니 키파는 에너지가 떨어져서, 이 "컴퓨터 FMC" 대회를 대신 구데기컵에 열기로 했습니다. 여러분은 프로그램을 작성해서, 이 프로그램을 컴퓨터 FMC 대회에 참가시켜야 합니다.
웬만큼 잘하는 사람이 평균 35회전을 한다고 하니 이것보다는 잘해야겠죠...!
첫째 줄에 333 큐브의 개수 N이 주어집니다. N은 1 혹은 30 000이며, N = 1인 데이터는 예제밖에 없습니다.
둘째 줄부터 9N개의 줄에 N개의 큐브가 주어집니다. 큐브 하나가 총 9줄에 걸쳐 주어지며, 333 큐브를 나타내는 54개의 정수가 예제 입력과 비슷한 형식으로 주어집니다. 큐브 조각의 색을 나타내는 정수는 1 이상 6 이하입니다. 각 면의 중앙 색은 예제 입력과 항상 같습니다.
입력으로 주어지는 모든 큐브는 면 회전만으로 맞출 수 있습니다.
N개의 줄에 풀이를 노트 란의 규정을 참고해서 출력합니다. 중앙 색이 1인 면이 위쪽 면(U 회전의 면), 2인 면이 앞쪽 면(F 회전의 면)입니다.
한 테스트 케이스에 대해서 점수는 다음과 같이 계산됩니다: 노트 란의 규정에 따라 계산된 무브 수의 총합을 N으로 나눈 값(평균)을 v라 합시다.
S가 222 222 이상이면 222 222점을 받습니다. 이외의 경우 테스트 케이스의 점수는 S와 최대 0.02까지 차이날 수 있습니다.
예제 이외의 테스트 케이스는 총 10개이며, 최종적으로 받게 되는 점수는 모든 테스트 케이스 점수의 최솟값입니다.
1 5 2 4 4 1 3 1 6 1 2 3 4 5 2 5 2 2 3 6 1 6 6 5 4 5 2 2 5 3 4 1 4 4 3 3 5 6 3 1 3 5 2 3 5 4 4 6 2 1 6 6 1 1 6
R2 D' U R' F D2 F' U2 F D2 F' B2 L' U F' L2 B R' U R D2 R' U' B R B D' B2 D
예시 입력의 이미지 설명
이 예제 입출력은 출제자가 직접 섞기 수열을 보고 회전 수를 최소한으로 한 풀이를 찾은 것으로, 29회전 풀이입니다.
섞기 수열은 다음과 같습니다: D U R2 B2 U R B' F2 L F2 U2 B R L2 D F2 B R2 L' F2 D2 R2 B2 U' F'. 잘 보고 따라 섞으면 예제 입력 1의 큐브가 나옵니다.
예시 풀이가 섞기 수열과 관련이 없음을 증명하기 위한 간략한 설명은 아래에 있습니다.
223: R2 D' U R' U2 B2 L' U F' L2 (10)
F2L-1: B D2 R' B R (15)
AB5C: B D' B2 D (19)AB5C Skeleton: R2 D' U R' U2 [*] B2 L' U F' L2 B D2 [**] R' B R B [***] D' B2 D
[*]: U2 R' D R U2 R' D' R (-3)
[**]: D2 R' U R D2 R' U' R (-4)
[***]: B' U F2 U' B U F2 U' (-2)
Insert at [**]AB3C Skeleton: R2 D' U R' U2 [*] B2 L' U F' L2 B R' U R D2 R' U' B R B D' B2 D (23)
[*]: U2 F D2 F' U2 F D2 F' (-2)
Solution: R2 D' U R' F D2 F' U2 F D2 F' B2 L' U F' L2 B R' U R D2 R' U' B R B D' B2 D (29)
이제 한 줄 한 줄 설명하겠습니다. 이 설명을 따라가실 경우 큐브를 직접 들고 이동을 직접 해 보는 것을 추천드립니다. 설명에서 언급되는 조각이 실제 어디로 이동하는지를 알 수 있습니다.
큐브를 관찰하다 보면 생각보다 연결되는 코너-엣지 쌍이 상당히 많다는 것을 알 수 있습니다. 원래는 222 블록을 먼저 맞추고 그 다음 223으로 넘어가지만, 페어 수가 너무 많았기 때문에 잘 활용하면 한꺼번에 223으로 갈 수 있겠다는 생각이 들었습니다.
여기까지 총 10회전입니다. 223에 10 회전이면 출제자 입장에서는 평균보다 약간 좋은 수준입니다.
F2L-1은 아무 색에서 시작하여 두 줄 맞춘 상태에서, 122 블록 한 곳이 비어 있는 형태입니다. 즉, 이 상태에서는
두 줄에서 122 블록 한 곳이 비게 됩니다. 이 상태에서는 노랑-빨강-초록(DRF) 코너가 노랑-빨강(DR) 엣지와 이미 연결되어 있기 때문에, 노란색이 네 개, 초록색이 있는 블록을 만들기로 했습니다.
설명이 길었는데, 여기까지 15 회전입니다. F2L-1까지 15 회전이면 출제자 평균 기준으로 좋은 페이스이긴 하나, 나머지 열 조각의 위치가 너무 나쁘면 버려질 수도 있습니다.
AB5C는 All But 5 Corners의 준말로, 현재 남은 다섯 개의 엣지와 다섯 개의 코너 중 다섯 개의 엣지를 전부 맞춰서 코너를 다섯 개 남기는 것입니다.
이 사항들에 유의하면서 B 면의 (옆 면까지 올바른) 십자가를 맞추려고 하면 됩니다. 남은 하나는 위치는 물론이고 십자가가 올바르다면 방향성까지 올바르기 때문에, B 면의 엣지 네 개를 맞추는 데 집중합니다.
좋습니다, 이제 딱 다섯 개의 코너만 맞추면 됩니다! 여기까지 19 회전입니다. AB5C 상황은 최소 5~8 회전에서 최대 20~26 회전까지 필요한 상황도 있기 때문에, 여기까지 몇 회전이 좋다 이런 기준은 남은 코너들의 위치를 봐야 알 수 있습니다. 하지만 이 단계까지 완료했을 때 19 회전이면 출제자의 최고 기록보다 딱 1 회전 많습니다!
스켈레톤은 거의 다 맞춘 큐브 상황을 만드는 회전 수열입니다. AB5C의 경우, 다섯 개의 코너를 제외하고 다 맞췄으므로 이제 스켈레톤을 작성할 수 있습니다. 그런데 어차피 코너만 다섯 개 바꾸는 게 마지막이라면, 바꾸는 위치가 옳다는 가정 하에 풀이의 어느 부분에서 바꿔도 상관없을 것입니다! 건드리는 건 바꿔야 하는 코너들밖에 없으니까요. 따라서 남은 과정은 스켈레톤을 훑으면서, 적용할 수 있는 공식이 있는지 단순히 확인하는 아주 고통스러운 과정입니다.
현재 큐브의 상태는 다음과 같습니다. 실제로 스티커를 붙이면 훨씬 보기 편하기 때문에 스티커를 붙였습니다.
AB5C 상황
어디로 가야 하는지를 조사한 결과 5-cycle인 것을 확인했고, 세 개씩 두 번 삽입하면 됩니다.
삽입 위치를 스켈레톤에 표시해 두었습니다: R2 D' U R' U2 [*] B2 L' U F' L2 B D2 [**] R' B R B [***] D' B2 D.
[*] U2 R' D R U2 R' D' R로 코너 두 개를 올바른 위치에 넣을 수 있습니다. 이 경우 [*] 앞의 U2는 공식 시작 부분의 U2와 만나 완전히 사라지고, 그 앞의 R'은 공식 시작 부분의 R'과 합쳐져 R2가 되기 때문에 총 3 회전이 줄어듭니다.
[**] D2 R' U R D2 R' U' R로 코너 두 개를 올바른 위치에 넣을 수 있습니다. 이 경우 [**] 앞의 D2는 공식 시작 부분의 D2와 만나 완전히 사라지고, [**] 뒤의 R'은 공식 끝 부분의 R과 만나 완전히 사라지면서 총 4 회전이 줄어듭니다.
[***] B' U F2 U' B U F2 U'로 코너 두 개를 올바른 위치에 넣을 수 있습니다. 이 경우 [***] 앞의 B는 공식 시작 부분의 B'와 만나 완전히 사라지면서 총 2 회전이 줄어듭니다.
회전 수를 가장 많이 줄이는 것은 [**]이므로 [**]에 삽입하겠습니다. 그러면 코너 두 개가 맞춰진 AB3C 상황이 됩니다.
AB5C 스켈레톤의 삽입 위치에 공식을 실제로 집어넣어서 AB3C 스켈레톤을 만듭니다. 현재까지 총 19 + 8 - 4 = 23 회전이고 아래와 같은 상태가 됩니다.
AB3C 상황
이제 실제로 삽입하면 곧바로 풀이를 얻을 수 있습니다: R2 D' U R' F D2 F' U2 F D2 F' B2 L' U F' L2 B R' U R D2 R' U' B R B D' B2 D. 놀랍게도 29 회전 풀이입니다!
FMC를 처음 시작하시는 경우 위의 예시 풀이가 큰 도움이 될 수도 있습니다.
스피드큐빙을 이미 어느 정도 즐겨 보신 분의 경우, 추천하는 FMC 튜토리얼은 이쪽(영어)입니다. 루빅스 큐브가 완전히 처음이시라면 이쪽(대부분 영어)을 추천드립니다.
큐브 매니아의 FMC 튜토리얼은 초심자들에게도 굉장히 친절하게 쓰여 있지만, 안타깝게도 카페 가입을 해야 볼 수 있습니다.
아래는 "E. 최소 회전 풀이"의 번역본이며, 아래에 문제에서 변경된 사항을 적어 두었습니다. 사라진 사항은 (削除) 취소선 (削除ここまで)으로, 추가된 사항은 굵은 글씨로 표시해 두었습니다.
clock() 등의 시간을 알 수 있는 C/C++ 헤더(자급).Contest > BOJ User Contest > 구데기컵 > 진짜 최종 구데기컵 2 2 $🔲^3$번