처음 에디토리얼을 써보는 유키=lewha0 입니다. 예전에도 한 번 기회가 있었는데, 에디토리얼 쓰는게 어떤 의미가 있나 싶어서 그냥 넘어갔었는데.. 문제 및 풀이를 간략히라도 한글로 번역해보는 의미가 있다고 하여 이렇게 올리게 되었습니다. ㅎㅎ
그림은 처음 넣어보는데 조금 잘리네요. 글 아래에 보면 첨부파일 목록이 있는데, 거기서 눌러 보시면 오른쪽도 보실 수 있습니다.
SRM 385는 올해의 마지막 SRM이었습니다. 한국 시간으로 새벽 1시에 있었지만, 우리나라 선수[?]들도 제법 많이 참가하였습니다. 여기에는 division 1만 나와 있지만, division 2까지 합치면 8+11=19명의 참가자가 있었습니다.
Writer는 Petr 인 것으로 알려졌습니다. Petr set은 level 1, 2가 비교적 쉽고 3이 극악의 난이도를 보여준다는 평이 있던데, 대체적으로 그런 평에 걸맞는 결과가 아니었나 생각됩니다. 대회 시작 전에 많은 사람들이 level 3의 배점이 1100점인 걸 보고 경악했었고, level 1, 2를 빠르게 풀어야겠다는 전략이 나왔는데.. 역시 적중한 것 같죠? level 3은 결국 아무도 풀지 못했고, 이 시간까지도 연습 방에 한 개의 솔루션(by ACRush!)만 살아남아 있는 상황입니다. 문제가 평이했던 덕인지, 챌린지도 비교적 적은 편이었습니다만, 저 같은 경우에는 광분하여 달린 나머지 세 번의 성공과 여섯 번의 실패를.. 제가 챌린지를 시도했던 솔루션들은 모두 systest 에서 fail이 떴는데, 아쉽네요 :( 세 개의 성공으로 막기만 했으면 SRM win을 할 수도 있었는데! ㅠㅠ
Level 1 (250)
몇 개의 단어로 이루어진 문장이 하나 주어집니다. 각 단어들 사이에 한 개 이상의 공백을 집어넣어, 전체 문장을 width 만큼의 폭 에 맞춰 넣으려고 합니다. 이 때 가능한 문장들(공백을 포함한) 중에서 사전 식으로 가장 앞서는 것을 구하는 문제입니다.
가장 긴 공백의 길이와 가장 짧은 공백의 길이는 1까지 차이날 수 있습니다. 즉, 공백을 한 쪽에 몰아서 넣으면 안되고 전체적으로 고르게 넣어야 합니다. 또한 사전 순서의 기준은 A < … < Z < _(공백) < a < … < z 으로 합니다. 단어의 개수는 최대 10개까지 가능하며, 각각의 단어는 최대 10자까지 입니다. width는 200 이하이며, 전체 단어 길이의 합 + 단어의 개수 - 1 이상입니다.
[spoiler="(풀이 보기)"] 그다지 어려울 건 없는 문제지만, 또 한편으로는 다양한 방법으로 풀 수 있는 문제이기도 합니다. 먼저 살펴볼 것은 공백 개수에 대한 제한입니다. 공백들을 고르게 넣어야 하기 때문에, 각 단어 사이에 최소한 (공백 개수)/(단어 개수 - 1) 만큼의 공백이 들어가야 합니다. 물론 (공백 개수) = width - (단어 길이의 총 합) 입니다. 이제 남아 있는 공백들을 적당히 넣어서 사전 식으로 가장 앞서는 것을 찾으면 됩니다.
가장 쉬운 방법은 모든 경우를 다 고려해 보는 것입니다. 단어의 개수가 최대 10개이기 때문에, 공백을 넣을 수 있는 위치는 최대 9개 입니다. 또, 각각의 위치에 넣을 수 있는 공백은 최대 한 개 뿐이므로, 가능한 경우의 수는 많아야 2^9 입니다. 실제로는 넣어야 할 공백의 개수가 정해져 있기 때문에, 이보다 경우가 더 적고요. 따라서 가능한 모든 경우를 시도해 보면서, 그 중에서 사전식으로 제일 앞서는 것을 구하면 됩니다.
혹은 그리디로도 이 문제를 풀 수 있습니다. 가능한 위치들 중에서 한 곳을 골라서 공백을 넣어보고, 이를 모든 위치에 대해 반복하면서 그 중에서 사전식으로 제일 앞서는 것을 구합니다. 그리고 이를 추가로 넣어야 할 공백의 개수만큼 반복하면 됩니다. 저는 단어의 개수가 50개라 생각했기 때문에 이 방법을 택했습니다만, 덕분에 시간이 제법 걸렸습니다.
아마 출제자가 의도한 방법 역시 그리디 방법일 것 같습니다. 사전 식으로 가장 앞서는 것을 구하려면, 문자열의 앞 부분부터 앞쪽으로 수정하면 됩니다. 즉, 단어를 앞에서부터 차례로 보면서, 그 단어가 알파벳 소문자로 시작한다면 그 앞에 공백을 넣어 줍니다. 그리고도 공백이 남는다면, 이번에는 단어를 뒤에서부터 차례로 보면서, 그 단어가 알파벳 대문자로 시작한다면 그 앞에 공백을 넣어 줍니다. 이렇게 하면 공백을 넣는게 좋을 경우는 앞에서부터 넣게 되고, 공백을 넣는게 나쁠 경우에는 뒤에서부터 넣게 되기 때문에 사전식으로 가장 앞서는 것을 구할 수 있습니다. 직접 짜본 것은 아니지만, 아마 될 것 같습니다 ^^;[/spoiler]
Level 2 (500)
n × m 크기의 미로가 주어집니다. 각각의 방은 네 가지의 타입이 있는데, A는 동서남북 모두로 문이 있는 방이고, B는 문이 없는 방이고, C는 남북으로만 문이 있는 방이고, D는 동서로만 문이 있는 방입니다. 방들 사이를 오갈 때에는 두 방에 달려있는 문의 방향이 맞아야 합니다. 예를 들어 (1, 1) 의 방에서 동쪽 (1, 2) 의 방으로 갈 때에는, (1, 1) 번 방의 동쪽으로 문이 있어야 하고, (1, 2) 번 방의 서쪽으로 문이 있어야 합니다. 방들 사이에서 한 칸을 이동할 때에는 1만큼의 시간이 듭니다.
또, 각각의 방에는 스위치가 있는데, 그 스위치를 누르면 해당 방이 포함되어 있는 열과 행의 모든 방이 90도만큼 회전하게 됩니다. 즉, C 타입의 방은 D 타입으로, D 타입의 방은 C 타입으로 바뀝니다. A, B 타입의 경우에는 바뀌지 않습니다. 또, 스위치를 누른 방은 해당 열과 해당 행으 교차점이기 때문에 두 번 회전하게 되고, 따라서 원래의 방향을 유지합니다. 스위치를 한 번 누를 때에도 1만큼의 시간이 듭니다.
이 때, (1, 1) 의 위치에서 시작하여, (n, m) 의 위치로 가는데 걸리는 최소 시간을 구하는 것이 문제입니다. 각 방에서는 스위치를 누를 수도 있고, 다른 방으로 이동할 수도 있습니다.
[spoiler="(풀이 보기)"] [/spoiler]
Level 3 (1100)
헐
마치며
ainu7 님 382, 384 올리시죠 ^^ ?
lewha0
처음 에디토리얼을 써보는 유키=lewha0 입니다. 예전에도 한 번 기회가 있었는데, 에디토리얼 쓰는게 어떤 의미가 있나 싶어서 그냥 넘어갔었는데.. 문제 및 풀이를 간략히라도 한글로 번역해보는 의미가 있다고 하여 이렇게 올리게 되었습니다. ㅎㅎ
그림은 처음 넣어보는데 조금 잘리네요. 글 아래에 보면 첨부파일 목록이 있는데, 거기서 눌러 보시면 오른쪽도 보실 수 있습니다.
SRM 385는 올해의 마지막 SRM이었습니다. 한국 시간으로 새벽 1시에 있었지만, 우리나라 선수[?]들도 제법 많이 참가하였습니다. 여기에는 division 1만 나와 있지만, division 2까지 합치면 8+11=19명의 참가자가 있었습니다.
Writer는 Petr 인 것으로 알려졌습니다. Petr set은 level 1, 2가 비교적 쉽고 3이 극악의 난이도를 보여준다는 평이 있던데, 대체적으로 그런 평에 걸맞는 결과가 아니었나 생각됩니다. 대회 시작 전에 많은 사람들이 level 3의 배점이 1100점인 걸 보고 경악했었고, level 1, 2를 빠르게 풀어야겠다는 전략이 나왔는데.. 역시 적중한 것 같죠? level 3은 결국 아무도 풀지 못했고, 이 시간까지도 연습 방에 한 개의 솔루션(by ACRush!)만 살아남아 있는 상황입니다. 문제가 평이했던 덕인지, 챌린지도 비교적 적은 편이었습니다만, 저 같은 경우에는 광분하여 달린 나머지 세 번의 성공과 여섯 번의 실패를.. 제가 챌린지를 시도했던 솔루션들은 모두 systest 에서 fail이 떴는데, 아쉽네요 :( 세 개의 성공으로 막기만 했으면 SRM win을 할 수도 있었는데! ㅠㅠ
Level 1 (250)
몇 개의 단어로 이루어진 문장이 하나 주어집니다. 각 단어들 사이에 한 개 이상의 공백을 집어넣어, 전체 문장을 width 만큼의 폭 에 맞춰 넣으려고 합니다. 이 때 가능한 문장들(공백을 포함한) 중에서 사전 식으로 가장 앞서는 것을 구하는 문제입니다.
가장 긴 공백의 길이와 가장 짧은 공백의 길이는 1까지 차이날 수 있습니다. 즉, 공백을 한 쪽에 몰아서 넣으면 안되고 전체적으로 고르게 넣어야 합니다. 또한 사전 순서의 기준은 A < … < Z < _(공백) < a < … < z 으로 합니다. 단어의 개수는 최대 10개까지 가능하며, 각각의 단어는 최대 10자까지 입니다. width는 200 이하이며, 전체 단어 길이의 합 + 단어의 개수 - 1 이상입니다.
[spoiler="(풀이 보기)"] 그다지 어려울 건 없는 문제지만, 또 한편으로는 다양한 방법으로 풀 수 있는 문제이기도 합니다. 먼저 살펴볼 것은 공백 개수에 대한 제한입니다. 공백들을 고르게 넣어야 하기 때문에, 각 단어 사이에 최소한 (공백 개수)/(단어 개수 - 1) 만큼의 공백이 들어가야 합니다. 물론 (공백 개수) = width - (단어 길이의 총 합) 입니다. 이제 남아 있는 공백들을 적당히 넣어서 사전 식으로 가장 앞서는 것을 찾으면 됩니다.
가장 쉬운 방법은 모든 경우를 다 고려해 보는 것입니다. 단어의 개수가 최대 10개이기 때문에, 공백을 넣을 수 있는 위치는 최대 9개 입니다. 또, 각각의 위치에 넣을 수 있는 공백은 최대 한 개 뿐이므로, 가능한 경우의 수는 많아야 2^9 입니다. 실제로는 넣어야 할 공백의 개수가 정해져 있기 때문에, 이보다 경우가 더 적고요. 따라서 가능한 모든 경우를 시도해 보면서, 그 중에서 사전식으로 제일 앞서는 것을 구하면 됩니다.
혹은 그리디로도 이 문제를 풀 수 있습니다. 가능한 위치들 중에서 한 곳을 골라서 공백을 넣어보고, 이를 모든 위치에 대해 반복하면서 그 중에서 사전식으로 제일 앞서는 것을 구합니다. 그리고 이를 추가로 넣어야 할 공백의 개수만큼 반복하면 됩니다. 저는 단어의 개수가 50개라 생각했기 때문에 이 방법을 택했습니다만, 덕분에 시간이 제법 걸렸습니다.
아마 출제자가 의도한 방법 역시 그리디 방법일 것 같습니다. 사전 식으로 가장 앞서는 것을 구하려면, 문자열의 앞 부분부터 앞쪽으로 수정하면 됩니다. 즉, 단어를 앞에서부터 차례로 보면서, 그 단어가 알파벳 소문자로 시작한다면 그 앞에 공백을 넣어 줍니다. 그리고도 공백이 남는다면, 이번에는 단어를 뒤에서부터 차례로 보면서, 그 단어가 알파벳 대문자로 시작한다면 그 앞에 공백을 넣어 줍니다. 이렇게 하면 공백을 넣는게 좋을 경우는 앞에서부터 넣게 되고, 공백을 넣는게 나쁠 경우에는 뒤에서부터 넣게 되기 때문에 사전식으로 가장 앞서는 것을 구할 수 있습니다. 직접 짜본 것은 아니지만, 아마 될 것 같습니다 ^^;[/spoiler]
Level 2 (500)
n × m 크기의 미로가 주어집니다. 각각의 방은 네 가지의 타입이 있는데, A는 동서남북 모두로 문이 있는 방이고, B는 문이 없는 방이고, C는 남북으로만 문이 있는 방이고, D는 동서로만 문이 있는 방입니다. 방들 사이를 오갈 때에는 두 방에 달려있는 문의 방향이 맞아야 합니다. 예를 들어 (1, 1) 의 방에서 동쪽 (1, 2) 의 방으로 갈 때에는, (1, 1) 번 방의 동쪽으로 문이 있어야 하고, (1, 2) 번 방의 서쪽으로 문이 있어야 합니다. 방들 사이에서 한 칸을 이동할 때에는 1만큼의 시간이 듭니다.
또, 각각의 방에는 스위치가 있는데, 그 스위치를 누르면 해당 방이 포함되어 있는 열과 행의 모든 방이 90도만큼 회전하게 됩니다. 즉, C 타입의 방은 D 타입으로, D 타입의 방은 C 타입으로 바뀝니다. A, B 타입의 경우에는 바뀌지 않습니다. 또, 스위치를 누른 방은 해당 열과 해당 행으 교차점이기 때문에 두 번 회전하게 되고, 따라서 원래의 방향을 유지합니다. 스위치를 한 번 누를 때에도 1만큼의 시간이 듭니다.
이 때, (1, 1) 의 위치에서 시작하여, (n, m) 의 위치로 가는데 걸리는 최소 시간을 구하는 것이 문제입니다. 각 방에서는 스위치를 누를 수도 있고, 다른 방으로 이동할 수도 있습니다.
[spoiler="(풀이 보기)"] [/spoiler]
Level 3 (1100)
헐
마치며
ainu7 님 382, 384 올리시죠 ^^ ?
16년 전