멀티탭이 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