개인적인 관점을 벗어나서 보면 우리의 가치는 결국 우리 다음 세대에 무엇을 남기는가로 결정된다.
그런데 무엇을 남기기는 커녕 다음 세대 다다음 세대의 것을 당겨서 쓰고 있다.
언제까지 가능할지는 모르겠지만 지금이라도 되돌려주기를 시작해야 하지 않을까?
5월 2010
05/13/2010
05/09/2010
2010.5월 구글 코드잼 예선문제 A번 풀이
작년 9월인가 구글 코드잼 문제 하나 풀이를 여기다 올린 적이 있는데
아무도 안 보는 거 같은데 뭐하러 쓰고 있는지는 모르겠지만
올해는 일단 참가도 했고(참가만 했음) 문제도 하나 풀었으니 풀이를 올려 본다.
작년 문제 해설은 자세히 썼었는데 요즘은 시간이 없으니 간략하게 간다.
일단 문제 원본은 여기에 있다.
코드잼 문제는 항상 시나락 까먹는 내용이 들어가는데 이번 문제는 별로 그런 거 없이 간단하다.
우선 기본 조건들을 정리해 보면 이렇다.
Snapper라는 장치가 있다. 한쪽은 전원(콘센트)에 꼽고, 다른 쪽엔 콘센트 구멍이 달려 있어서 전기를 쓰는 기계를 여기에 연결할 수 있다.
즉 이 문제의 Snapper = 일반적으로 사용하는 멀티탭과 완전히 같다. 앞으로는 그냥 멀티탭이라 칭한다.
멀티탭은 ON/OFF가 가능하다. on이면 자기가 가진 콘센트 구멍으로 전기를 공급하고, off면 차단한다. 일반적인 멀티탭의 스위치와 동일한 역할인데, 단지 스위치를 손으로 조작하는 방식이 아니라, 손가락 튕기는 소리가 날 때마다 on/off가 바뀌는 방식의 스위치가 달려 있다. (박수치면 소리 나오는 인형 그런 식이다.)
멀티탭의 on/off를 손으로 직접 조작하는 것이 아니라 손가락 튕기는 소리로 조작하는 것이기 때문에, 손가락을 튕겨서 멀티탭을 끄거나 켜고 싶으면 그 순간 그 멀티탭에는 전기가 공급된 상태여야 한다. ( 소리 듣고 on/off 스위치를 조작시켜 주는 회로가 동작하려면 일단 전기가 필요하니까 )
약간 상식과 다르게 동작하므로 조심해야 할 부분이 있는데, 멀티탭의 on/off 상태를 바꾸기 위해 손가락을 딱 튕긴 바로 그 순간에 특정 멀티탭에 전기가 공급되고 있었다면 그 멀티탭의 on/off 전환 동작이 이루어진다.
- 이게 무슨 말인가 하면
- 첫번째 멀티탭에 두번째 멀티탭이 꼽혀 있는 상태에서 전기가 두번째 멀티탭까지 통하고 있을 경우. (첫번째 멀티탭은 on이라서 두번째 멀티탭으로 전기를 보내주고 있음. 두번째 멀티탭의 on/off상태는 여기서는 상관없음)
- 손가락을 튕겨서 첫번째 멀티탭을 off로 바꾸면 두번째 멀티탭까지 전기가 공급되지 않으니 두번째 멀티탭은 손가락 튕기는 소리를 듣고 작동하는 데 필요한 전기가 없어서 on/off 전환이 이루어지지 않을 거라고 생각할 수 있는데
- 그렇지 않고, 각각의 멀티탭은 손가락 튕기는 소리가 나는 그 한 순간에 전기가 공급되고 있다면 그 전기를 이용해서 각각 on/off 전환이 일어난다는 이야기이다.
- 즉 각 멀티탭은 일단 전원을 공급받았다면 다음번 딱 한번의 on/off 전환에 필요한 한번의 전기를 콘덴서 같은 데다 저장해 둔다는 식으로 생각하면 대충 맞다.
바로 위 항목을 다시 정리해 보면, 손가락을 딱 튕기면 다음 두 가지 상태(phase)가 순서대로 발생한다.
1) on/off 전환 단계 : 각 멀티탭에 전기가 공급된 상태라면 on/off상태가 바뀜. 전기가 공급되지 않는 상태라면 on/off 상태 변경 없음.
2) 전기를 받아서 보내는 단계 : 앞 1)에서 결정된 각 멀티탭의 on/off 상태에 따라, 벽의 콘센트에서 처음 공급된 전기가 멀티탭들을 타고 흘러서, 가장 처음 off상태인 멀티탭 바로 직전까지 전기가 통하게 됨.
멀티탭의 특성은 이 정도이고, 문제는 이거다.
- N개의 멀티탭이 연쇄적으로 연결되어 있다.
- 첫번째 멀티탭은 벽의 콘센트에 꼽혀 있어서 항상 전기를 공급받고 있다.
- 마지막(N번째) 멀티탭에는 전구가 꼽혀 있다. 전구에는 스위치가 없고 전기가 들어오면 바로 불이 들어온다.
- 모든 멀티탭의 on/off 스위치는 처음에는 동일하게 off로 되어 있다.
- 이제 손가락을 K번 튕겨서 멀티탭의 on/off상태들을 변경시킨다.
- K번 손가락 튕긴 후, 전구에 불이 들어와 있을까 꺼져 있을까?
간단히, N=2이고 K=3인 경우에 대해 생각해 보자. 즉 멀티탭이 두 개 연결되어 있고 전구는 두번째 멀티탭에 달려 있고, 손가락은 세 번 튕긴다. 초기에는 모든 멀티탭이 off 상태이다.
0) 초기상태
1) 손가락을 한번 튕겼을 때 :
- on/off 전환 단계 : (첫번째 멀티탭은 벽 콘센트에 바로 꼽혀 있으므로 전원을 항상 공급받고 있으므로 손가락 튕기는 소리에 언제나 반응하여 on/off전환이 가능함.) off->on 상태가 됨. 두번째 멀티탭은 손가락을 튕긴 시점에는 전기가 공급되지 않았으므로 상태변화 없음.
- 전기 흘러가는 단계 : 첫번째 멀티탭이 on이고 두번째 멀티탭은 off이므로 전기는 두번째 멀티탭 직전까지 공급되는 상태가 됨.
- 정리하면 : 스위치는 첫번째멀티탭:on, 두번째멀티탭:off. 전기는 첫번째멀티탭까지만 흐름.
2) 손가락을 또 튕겼을 때 :
- on/off 전환 단계 : 첫번째 멀티탭은 off 상태가 됨. 두번째 멀티탭은 손가락 튕기는 시점에는 전기가 공급되고 있었으므로 off->on으로 상태가 바뀜.
- 전기 흘러가는 단계 : 첫번째 멀티탭이 off상태이므로 전기는 그 전까지만 흘러감. 즉 아무 멀티탭에도 전기가 공급되지 않음.
- 정리하면 : 스위치는 첫번째멀티탭:off, 두번째멀티탭:on, 전기는 첫번째멀티탭까지도 흐르지 않음.
3) 손가락을 또 튕겼을 때 :
- on/off 전환 단계 : 첫번째 멀티탭은 on상태가 됨. 두번째 멀티탭은 손가락 튕기는 시점에는 전기가 공급되지 않았으므로 변동 없음 (on상태 그대로)
- 전기 흘러가는 단계 : 첫번째 멀티탭이 on이고 두번째 멀티탭도 on이므로 전기는 두번째 멀티탭이 가진 콘센트까지 흘러서 거기 꼽힌 전구까지 흐름. 전구에 불 들어옴.
- 정리하면 : 스위치는 on,on. 전기는 끝까지 흐름.
따라서 N=2, K=3 일 때 전구는 ON상태가 된다는 것이 답이다.
실제 코드잼 문제는 [N값과 K값] 들이 많이(1만 개) 주어지고, 각 경우에 대한 전구의 ON/OFF 여부(당연히 1만 개)를 알아내는 것이다.
각 멀티탭을 별개의 객체로 모델링하고 (N개의 객체 생성), 손가락을 튕길 때마다 각 멀티탭의 동작을 시뮬레이션하면(즉 N개의 객체마다의 메소드를 호출해서 각 객체의 on/off상태 변경 및 연결된 객체로 전기를 보내주는 여부를 변경시킴) K번 손가락 튕긴 후 상태를 알아내는 것 자체는 간단하다.
그런데 그런 식으로 프로그램을 만들면 망한다. 방법은 전혀 틀리지 않았지만, 코드잼 문제는 입력파일([N값과 K값] 이 1만 개 기록된 파일) 을 받아서 몇 분 안에 출력파일 (1만 개의 경우에 대한 전구의 on/off여부)을 다시 제출해야 하므로 그때까지 결과가 안 나오면 탈락이다. 여기서 1 ≤ N ≤ 30, 0 ≤ K ≤ 108 과 같은 식이 되니까 (멀티탭 최대 30개, 손가락 튕기는 횟수는 최대 1억 번) 그런 걸 1만 번 반복하면 시간이 모자라겠지.
그래서 다른 방법을 생각해 본다.
다음은 이 문제 풀면서 스케치했던 내용이다.
멀티탭이 4개이고, 4번째 멀티탭에 전구가 달린 경우의 그림이다.
왼쪽의 숫자가 0일 때가 초기상태이고, 숫자 1은 손가락을 한 번 튕긴 후의 상태, 2는 손가락을 두 번 튕긴 후의 상태이다.
화살표가 위를 향한 것은 멀티탭이 on 상태이고, 아래를 향한 것은 off 상태를 나타내며, 화살표 없이 빈 것은 off와 동일하다. (귀찮아서 안 그린 것일 뿐임)
멀티탭 사이를 잇는 선은 전기가 통하고 있음을 나타낸다.
다시 멀티탭에 대해 생각해 보면, 하나의 멀티탭이 가지는 속성은 다음의 두 가지로 나누어볼 수 있다.
- 그 멀티탭의 스위치가 on인가 off인가
- 그 멀티탭으로 전기가 공급되는 상태인가 아닌가
각각 2가지 경우가 있을 수 있으므로 2*2=4가지의 경우가 나오고, 이 중 그 멀티탭에 꽂힌 기기로 전기를 보내줄 수 있는 경우는 4가지 중 한 가지 경우뿐이다. (스위치가 on이고 전기도 공급되는 경우)
따라서 우리가 특정 순간에 각 멀티탭에서 알고 싶은 정보는 이것이고
- 그 멀티탭이 자신에게 꽂힌 기기에게 전기를 공급해 주는 상태인가 아닌가 (즉 그 멀티탭에서 출력전원이 나오는가 아닌가).
멀티탭 N개가 직렬연결되어 있으므로, 결국 K번 손가락 튕긴 뒤의 시점에 N번째 멀티탭이 전기를 제공해줄 수 있는가 아닌가(출력전원을 제공하는가 아닌가)만 구하면 된다.
우선 첫번째 멀티탭을 보면
- 입력전원 : 벽의 콘센트에서 항상 전기를 공급받음.
- 출력전원 : 스위치가 on이면 공급, off면 공급하지 않음.
따라서 입력전원은 결과의 경우의 수에 영향을 주지 못하고, 스위치의 on/off여부에 따라서만 출력전원의 여부가 결정된다.
-> 출력전원은 손가락을 튕길 때마다 번갈아서 공급되었다가 되지 않았다가 한다. 즉 [매 2번째 - 1] 의 손가락 튕김(이제 snap이라고 한다)이 있을 때마다 출력전원이 발생한다.
(여기서 '-1'이 필요한 것은 맨 처음 상태에는 스위치가 off였기 때문에 1번만 snap하면 on이 되기 때문이다. 그 뒤로는 두 번씩 더 snap할 때마다 on 된다.)
첫번째 멀티탭에 연결된 두번째 멀티탭을 보면
- 입력전원 : 첫번째 멀티탭에서 전기를 공급받음. 이때 첫번째 멀티탭으로부터의 전원공급은 매 2번째의 snap시에 인가된다.
- 출력전원 : 스위치의 on/off여부에 따라 출력전원의 공급여부가 결정되는데, 스위치의 on/off 토글은 입력전원이 인가된 상태에서 snap이 발생할 때만 일어난다.
입력전원의 인가가 매 2번째 snap마다 일어나므로, 스위치의 on/off 토글도 매 2번째 snap에 발생된다.
-> 결국 출력전원은 [입력전원의 인가:매 2번째 snap] * [스위치의 on/off 토글:매 2번째 snap] -> [매 4번째 snap - 1] 번 snap시에 출력전원이 발생한다.
여기까지 그림에서 0~3번째까지를 보면 알 수 있다.
그 뒤의 멀티탭에 대해서도 마찬가지이며, 정리하면
N번째 멀티탭에서 출력전원이 발생하는 조건 : x * (2^N) - 1 번째 snap 후 N번째 멀티탭에서 출력전원이 발생한다.
(여기서 x는 0보다 큰 정수. 2^N 은 2의 N승을 의미함.)
그림에서 멀티탭이 4개이므로 x * 16 - 1 번째 snap이 발생했을 때 4번째 멀티탭에서 출력전원이 발생한다.
즉 15번째, 31번째, 47번째... 의 snap의 경우가 된다. 그림에서도 15번째에 맨 마지막 전구까지 전원이 연결되었음을 볼 수 있다.
따라서, 멀티탭이 30개이고 손가락을 1만 번 튕긴 후 30번째 멀티탭에 연결된 전구의 on/off 여부를 알려면
적당한 x를 찾아내되, 다음과 같은 식이 되면 전구가 켜지는 snap횟수들 사이에 1만번 snap이 위치하므로 전구는 꺼진 상태가 되고
x * (2^30) - 1 < 10000 < (x+1) * (2^30) - 1
다음과 같은 식이 되면 전구가 켜지는 snap 회수가 1만 번 snap과 겹치므로 전구는 켜진 상태가 된다.
x * (2^30) - 1 = 10000
적당한 x를 구하는 것은 나눗셈을 이용하면 간단하므로 풀이는 생략하고, 바로 코드를 첨부하면 다음과 같다.
#!/usr/bin/perl
use strict;
use warnings;
use FileHandle;
my $dataFileName = 'A-small-attempt0.in';
my $outFileName = 'A-small-attempt0.out';
my @Ns;
my @Ks;
my @Answers;
makeStructure();
calculate();
printout();
# read input file and make structure which has T, N, and K
sub makeStructure {
my $ifh = new FileHandle( $dataFileName, 'r' );
my $linecount = 0;
my $T = 0;
while (<$ifh>) {
$linecount++;
chomp;
my $line = $_;
$line = trim($line);
next if $line =~ m|^#| or $line =~ m|^$|;
if ( $linecount == 1 ) {
$T = $line;
}
else {
my ( $N, $K ) = split " ", $line;
push @Ns, $N;
push @Ks, $K;
}
}
if ( $T != @Ns ) {
die "The T value and actual N/K line counts are different.";
}
}
# calculate
sub calculate {
for ( my $i = 0 ; $i < @Ns ; $i++ ) {
my $N = $Ns[$i];
my $K = $Ks[$i];
my $base = 2**$N;
#my $K1 = int( $K / $base ) * $base - 1;
my $K2 = ( int( $K / $base ) + 1 ) * $base - 1;
if ( $K == $K2 ) {
#print "calc case #" . ( $i + 1 ) . ":[ ON] $K1 < $K = $K2\n";
$Answers[$i] = "ON";
}
else {
#print "calc case #" . ( $i + 1 ) . ":[OFF] $K1 < $K < $K2\n";
$Answers[$i] = "OFF";
}
}
}
sub printout {
my $ofh = new FileHandle( $outFileName, 'w' );
for ( my $i = 0 ; $i < @Answers ; $i++ ) {
my $nth = $i + 1;
print $ofh "Case #" . $nth . ": " . $Answers[$i] . "\n";
}
}
sub trim {
my $string = shift;
$string =~ s/^\s+//;
$string =~ s/\s+$//;
return $string;
}
코드에서 핵심은 다음 행과
my $base = 2**$N;
다음 행들이며
if ( $K == $K2 ) {
#print "calc case #" . ( $i + 1 ) . ":[ ON] $K1 < $K = $K2\n";
$Answers[$i] = "ON";
}
코드에서 다음의 3줄을 주석해제하면 위에서 잠깐 예를 든 부등식의 형태로 결과를 볼 수 있다. 아니면 결과만 찍는다.
#my $K1 = int( $K / $base ) * $base - 1;
#print "calc case #" . ( $i + 1 ) . ":[ ON] $K1 < $K = $K2\n";
#print "calc case #" . ( $i + 1 ) . ":[OFF] $K1 < $K < $K2\n";
Recent Comments