[이상규]

안녕하세요,

뉴 보물섬 관련하여 질문 드립니다.

1. 안내판이 놓인 길 밖에, 안내판에 적힌 이름과 같은 이름의 보물상자가 있을 수 있나요?
즉, x | (y | ([x]x))와 같은 지도도 유효한 지도인가요?

이 경우 "같은 이름의 보물 상자는 같은 열쇠로 열리"므로
x는 은괴(-)로 열 수 없고,
x := (-, -)
y := (((-, -), (-, -)), -)
로 열어 {(-, -), (((-, -), (-, -)), -)}이 답이 된다고 이해하면 될까요?

2. 준비물 크기가 열쇠들의 가지 개수로 정의된다고 하였는데, '열쇠의 총 개수'와 '각 열쇠 크기 합' 중 어느 기준이 우선되나요?

예컨대 (x | ((y | [z]z) | x))와 같은 지도를 생각할 때,
x가 열쇠 (a, b), z가 열쇠 c로 열린다고 하면, y는 ((c, c), ((a, b), a)로 열립니다.
이때
i) a = -, b = -, c = (-, -)라 하면
열쇠들은 = {(-, -), (((-, -), (-, -)), ((-, -), -))}가 되고,

ii) a = -, b = -, c = -라 하면
열쇠들은 {-, (-, -), ((-, -), ((-, -), -))}가 됩니다.

열쇠의 총 개수는 두 개인 i)가 세 개인 ii)보다 작지만,
은열쇠의 leaf 총 개수는 8개인 ii)가 9개인 i)보다 작습니다.
이와 같은 경우에는 i)와 ii) 중 어느 준비물의 크기가 더 작다고 보아야 하나요?

더 나아가, '각 열쇠의 크기'를 어떻게 계산해야 하나요?
예를 들어 leaf(Bar) 개수만 세면 (-, (-, (-, -)))와 ((-, -), (-, -))는 모두 4개입니다.
하지만 t의 constructor의 개수를 세면 왼쪽은 Node 3개 + Bar 4개 = 7개, 오른쪽은 Node 2개 + Bar 4개 = 6개로 왼쪽이 더 큽니다.
또한 '가지' 개수라는 표현을 Node에는 가지가 2개, Bar에는 가지가 0개 있다고 해석하면 왼쪽은 6개, 오른쪽은 4개가 될 것입니다.

위 정의들 중 어떤 방식으로 각 열쇠의 크기를 계산해야 하는지,
그리고 그 크기의 합을 기준으로 준비물 크기를 정하는 것인지 궁금합니다.

3. 지도의 최대 크기나 최대 실행 시간에 대한 제한이 있을까요?
크기가 최소인 준비물을 무차별 대입으로 구하게 되면 변수가 많은 지도에 대해 실행 시간이 엄청나게 오래 걸릴 듯 한데, 보다 빠른 알고리즘을 고안해야 할지 궁금합니다.

감사합니다.

이상규 올림

[안중원]

안녕하세요, 조교 안중원입니다.

1. 보물상자는 언제나 그 이름이 적힌 안내판이 놓인 길 안에 놓여있습니다. 그렇지 않은 경우는 고려하지 않아도 됩니다.

2. 열쇠 꾸러미의 크기는 열쇠들에 들어가는 Bar의 총 개수를 기준으로 비교합니다. 잘 생각해보시면, 두 열쇠의 Bar의 개수가 같으면 Node의 개수 또한 같다는 것을 알 수 있습니다. 제시하신 예시에서도 양쪽 열쇠 모두 Node는 3개, Bar는 4개입니다.

3. 제한시간은 15초, 필요한 열쇠 꾸러미 크기(Bar 개수)는 최대 50개 이하인 테스트 케이스로 채점합니다.

감사합니다.
_________________
TA 안중원
TA e-mail: ta310@ropas.snu.ac.kr
personal e-mail: jwahn@ropas.snu.ac.kr

[안중원]

안녕하세요, 조교 안중원입니다.

3번 답변에 대해 정정드립니다.

실행시간은 엄격히 제한되어있지 않고, 열쇠 꾸러미 크기 또한 특별한 제한이 없다고 생각하고 풀어주시기 바랍니다.

채점과정에서 프로그램이 무한반복에 빠진 것으로 의심되면 임의로 시간 초과로 간주하여 오답 처리될 수 있습니다.

감사합니다.
_________________
TA 안중원
TA e-mail: ta310@ropas.snu.ac.kr
personal e-mail: jwahn@ropas.snu.ac.kr

[이상규]

안녕하세요,
답변 감사합니다.

Bar의 총 개수가 같다면 어느 열쇠 꾸러미를 답으로 내든 상관없나요?
예컨대 {-, (-, -), (-, (-, -))}와 {-, ((-, -), (-, (-, -)))}이 모두 답이 되는 열쇠 꾸러미라면,
오른쪽 답이 '열쇠 개수'가 2개로 더 적지만 'Bar의 총개수'는 모두 6개로 같으므로 둘 다 답이 된다고 보면 될까요?

이상규 올림

[안중원]

말씀하신대로 가장 작은 꾸러미들 가운데 아무거나 답으로 내놓으면 됩니다.

감사합니다.
_________________
TA 안중원
TA e-mail: ta310@ropas.snu.ac.kr
personal e-mail: jwahn@ropas.snu.ac.kr