안녕하세요.
오랜만에 에디토리얼(!)을 쓰는 욱입니다. TCO 2010 Qualification Round 1
250 - GirlsAndBoys
문제
걸들과 보이들이 일렬로 서있습니다. 인접한 두 명의 위치를 바꾸는 연산을 최소 몇 번 해야, 남녀가 서로 붙어있는 쌍의 수를 최소화할 수 있을까요?
풀이
쉬운 문제입니다. 최소화..는 훼이크! 어떠한 경우에도 이 최소값은 0 또는 1 이라는 것을 쉽게 관찰해낼 수 있고, 이 관찰만 얻어 내면 문제 풀이는 끝. 모든 사람이 다 같은 성별인 경우에는 0일 것이고, 남자와 여자가 둘 다 있는 경우는 당연히 1입니다(0인것은 불가능하고, GG...GGBB..BB 또는 BB...BBGG...GG 꼴로 항상 바꿀 수 있으므로).
그러면 문제는 주어진 sequence를 인접한 두 element만 바꿔서 정렬하기 위해 필요한 최소 교환 횟수를 물어보는 게 됩니다. B...BG...G 로 정렬하는 경우나 G..GB...B로 정렬하는 경우 중 최소값이 답이 될 테고, 이 문제는 Bubble Sort 를 수행했을 때의 교환 횟수와 일치한다는 것을 쉽게 알 수 있어요. G랑 B밖에 없으므로 Insertion Sort를 하듯이 O(N)으로 삽입될 위치를 알아내서 거기까지 shift하기 위해 필요한 교환 횟수의 합을 구하는 방식도 가능합니다.
500 - RobotSimulation
문제
무한 격자가 있습니다. URLD로 이루어진 길이 (maximum) 10짜리 스트링이 있는데 로봇은 앞에서부터 한 문자씩 읽으면서 위, 오른쪽, 왼쪽, 아래로 한 칸 이동합니다. 이런 movement를 times 번 반복할 때, 로봇이 밟은 적이 있는 칸의 개수는 몇 개일까요? (times 는 200,000,000 이하)
풀이
이런 문제를 읽으면 times가 작은 수였으면 좋겠다...라는 꿈을 꿉니다. 하지만 2억이잖아? 그냥 naive하게 돌리면 아마 안될거야...
흠, 어쨌거나 이 문제도 사소한 관찰 하나가 필요합니다. 이걸 얼마냐 빨리 떠올리느냐가 문제의 키포인트가 아닌가 싶네요.
지금 문제점은 로봇이 한 번 스트링을 쫙 훑었을 때 밟는 칸들은 예전에 이미 밟은 적이 있을 수 있기 때문에 중복이 있을 수 있다는 거에요. 그러면 밟은 적 없는 신천지, 새로운 칸들의 수에 주목해 봅시다. 근데 이게 반복할 때마다 항상 일정하지는 않아서 아직은 난감합니다.
하지만 잘 생각해보면 어느 순간부터는 '스트링을 한 번 훑었을 때 새로운 칸의 수' 가 일정해야 합니다. 왜냐고요? 로봇의 command string의 길이가 10으로 bounded 되어있고 똑같은 스트링을 반복하니까, 새롭게 밟은 칸의 수도 처음 몇 번을 제외하면 나중에는 수렴해서 일정한 수가 계속 나타나겠죠.
그러면 처음 몇 번은 그냥 쌩으로 합니다. 적당한 크기의 2차원 배열 잡아서 처음 K 회는 로봇의 움직임을 시뮬레이션 하고 (칸 중복 체크도 하고..) 현재까지 밟은 칸의 수를 셉니다(이 값을 initial 라고 합시다.) 그러면 이 다음부터는 한 번 스트링을 훑을 때마다 새롭게 밟은 칸의 수가 일정하다고 할 수 있으므로, 한 번 더 시뮬레이션 해서 새롭게 밟은 칸의 수를 구합니다(이 값을 additional 이라고 합시다). 그러면 times번 스트링을 훑었을 때 전체 밟은 칸의 수는 initial + (times - K) * additional 임을 쉽게 알 수 있습니다. K < times 인 경우는 조금 조심해 줘야겠죠.
여기까지 생각하는건 그닥 어렵지 않은데, 그럼 몇 번이면 될까요? (즉, K를 몇으로 잡으면 안전할까?) 이는 조금 생각해 볼만한 문제인데 대회중에는 시간이 없으므로 시간이 허락하는 한에서 안전하게 적당히 해주면 됩니다. 저같은 경우는 스트링의 최대 길이가 10이므로 10번만 넘어가면 수렴할 것이라 생각했고, K=15로 잡았습니다. 이제 이에 맞는 적당한 2차원 배열을 만들어 주면 initial 구하는거야 얼마 안 걸리니까 답을 구할 수 있겠죠. 아니면 뭐 set 써도 되구요.
문제 풀때는 안전하게 적절히 이 K값을 고르면 되는데.. 일단 이 문제를 풀기 위한 해법은 여기까지면 충분하고요, 조금 더 머리를 굴려보기 위해 (지금은 시간이 많으니...?) 몇 가지를 좀 더 생각해 봅시다. 가능한 K의 최소값은 얼마일까요? 증명할 수 있을까요? (저도 대회 끝나고 나중에 혼자 곰곰이 생각해 본 거라.. 대회 때에는 이런거 생각하면 점수만 깎이므로(?) )
정답부터 말하면 3 입니다. 일반화해서, 로봇의 movement string의 길이를 n이라고 할 때, K >=
wookayin
안녕하세요.
오랜만에 에디토리얼(!)을 쓰는 욱입니다. TCO 2010 Qualification Round 1
250 - GirlsAndBoys
문제
걸들과 보이들이 일렬로 서있습니다. 인접한 두 명의 위치를 바꾸는 연산을 최소 몇 번 해야, 남녀가 서로 붙어있는 쌍의 수를 최소화할 수 있을까요?
풀이
쉬운 문제입니다. 최소화..는 훼이크! 어떠한 경우에도 이 최소값은 0 또는 1 이라는 것을 쉽게 관찰해낼 수 있고, 이 관찰만 얻어 내면 문제 풀이는 끝. 모든 사람이 다 같은 성별인 경우에는 0일 것이고, 남자와 여자가 둘 다 있는 경우는 당연히 1입니다(0인것은 불가능하고, GG...GGBB..BB 또는 BB...BBGG...GG 꼴로 항상 바꿀 수 있으므로).
그러면 문제는 주어진 sequence를 인접한 두 element만 바꿔서 정렬하기 위해 필요한 최소 교환 횟수를 물어보는 게 됩니다. B...BG...G 로 정렬하는 경우나 G..GB...B로 정렬하는 경우 중 최소값이 답이 될 테고, 이 문제는 Bubble Sort 를 수행했을 때의 교환 횟수와 일치한다는 것을 쉽게 알 수 있어요. G랑 B밖에 없으므로 Insertion Sort를 하듯이 O(N)으로 삽입될 위치를 알아내서 거기까지 shift하기 위해 필요한 교환 횟수의 합을 구하는 방식도 가능합니다.
500 - RobotSimulation
문제
무한 격자가 있습니다. URLD로 이루어진 길이 (maximum) 10짜리 스트링이 있는데 로봇은 앞에서부터 한 문자씩 읽으면서 위, 오른쪽, 왼쪽, 아래로 한 칸 이동합니다. 이런 movement를 times 번 반복할 때, 로봇이 밟은 적이 있는 칸의 개수는 몇 개일까요? (times 는 200,000,000 이하)
풀이
이런 문제를 읽으면 times가 작은 수였으면 좋겠다...라는 꿈을 꿉니다. 하지만 2억이잖아? 그냥 naive하게 돌리면 아마 안될거야...
흠, 어쨌거나 이 문제도 사소한 관찰 하나가 필요합니다. 이걸 얼마냐 빨리 떠올리느냐가 문제의 키포인트가 아닌가 싶네요.
지금 문제점은 로봇이 한 번 스트링을 쫙 훑었을 때 밟는 칸들은 예전에 이미 밟은 적이 있을 수 있기 때문에 중복이 있을 수 있다는 거에요. 그러면 밟은 적 없는 신천지, 새로운 칸들의 수에 주목해 봅시다. 근데 이게 반복할 때마다 항상 일정하지는 않아서 아직은 난감합니다.
하지만 잘 생각해보면 어느 순간부터는 '스트링을 한 번 훑었을 때 새로운 칸의 수' 가 일정해야 합니다. 왜냐고요? 로봇의 command string의 길이가 10으로 bounded 되어있고 똑같은 스트링을 반복하니까, 새롭게 밟은 칸의 수도 처음 몇 번을 제외하면 나중에는 수렴해서 일정한 수가 계속 나타나겠죠.
그러면 처음 몇 번은 그냥 쌩으로 합니다. 적당한 크기의 2차원 배열 잡아서 처음 K 회는 로봇의 움직임을 시뮬레이션 하고 (칸 중복 체크도 하고..) 현재까지 밟은 칸의 수를 셉니다(이 값을 initial 라고 합시다.) 그러면 이 다음부터는 한 번 스트링을 훑을 때마다 새롭게 밟은 칸의 수가 일정하다고 할 수 있으므로, 한 번 더 시뮬레이션 해서 새롭게 밟은 칸의 수를 구합니다(이 값을 additional 이라고 합시다). 그러면 times번 스트링을 훑었을 때 전체 밟은 칸의 수는 initial + (times - K) * additional 임을 쉽게 알 수 있습니다. K < times 인 경우는 조금 조심해 줘야겠죠.
여기까지 생각하는건 그닥 어렵지 않은데, 그럼 몇 번이면 될까요? (즉, K를 몇으로 잡으면 안전할까?) 이는 조금 생각해 볼만한 문제인데 대회중에는 시간이 없으므로 시간이 허락하는 한에서 안전하게 적당히 해주면 됩니다. 저같은 경우는 스트링의 최대 길이가 10이므로 10번만 넘어가면 수렴할 것이라 생각했고, K=15로 잡았습니다. 이제 이에 맞는 적당한 2차원 배열을 만들어 주면 initial 구하는거야 얼마 안 걸리니까 답을 구할 수 있겠죠. 아니면 뭐 set 써도 되구요.
문제 풀때는 안전하게 적절히 이 K값을 고르면 되는데.. 일단 이 문제를 풀기 위한 해법은 여기까지면 충분하고요, 조금 더 머리를 굴려보기 위해 (지금은 시간이 많으니...?) 몇 가지를 좀 더 생각해 봅시다. 가능한 K의 최소값은 얼마일까요? 증명할 수 있을까요? (저도 대회 끝나고 나중에 혼자 곰곰이 생각해 본 거라.. 대회 때에는 이런거 생각하면 점수만 깎이므로(?) )
정답부터 말하면 3 입니다. 일반화해서, 로봇의 movement string의 길이를 n이라고 할 때, K >=
14년 전