문제

1014번: 컨닝

최백준은 컨닝을 방지하기 위해서 다음과 같은 전략을 세웠다. 모든 학생은 자신의 왼쪽, 오른쪽, 왼쪽 대각선 위, 오른쪽 대각선 위, 이렇게 총 네 자리에 앉아있는 친구의 답지를 항상 베낀다고 가정한다. 따라서, 자리 배치는 모든 학생이 컨닝을 할 수 없도록 배치되어야 한다.
www.acmicpc.net

풀이 해설

비트 마스킹

한 열에 학생들이 8명 앉아 있고, 오른쪽을 기준으로 1, 3, 6번째 자리의 학생들이 앉은 경우를 이진수로 표현하게 되면

$$ 00100101_{(2)} $$

현재 열의 상태를 위와 같이 표현할 수 있고, 이는 십진수로는 37으로 나타낼 수 있고, 총 8자리 임으로 우리는 $2^{8}$의 숫자, 0 ~ 255의 숫자로 현재 열의 상태를 표현할 수 있다. 오로지 현재 열의 앉은 상태만을 고려하고 앞자리 혹은 뒷자리에 앉은 인원과 앉을 수 없는 자리 여부 등은 탐색을 진행하면서 고려하면 된다. 열을 기준으로 앞 열부터 탐색을 진행하던, 뒷 열부터 탐색을 진행하던 크게 상관은 없고 이번 풀이에서는 앞 열부터 탐색을 진행하려 한다.

점화식

기본적으로 다이나믹 프로그래밍을 이용하여 풀면 되며, 현재 열 $i$의 앉은 상태 $j$에서의 $i$열부터 맨 앞열 까지의 앉은 인원의 최대 수를 $A_{i, j}$라 한다면 두가지 조건 ①, ②에 대해서

  1. 현재 열 $j$에 부서진 자리가 앉는 학생이 없고, 붙어 앉는 학생이 없는 경우

  2. 현재열의 자리 $j$가 앞 열의 자리 $k$ 상태에서 컨닝이 불가능 한 경우

$$ A_{i, j}= \begin{cases} 0, & \text{if } j \text{가 ①, ②에 위배} \\ (j \text{의 2진수 표현에서 1의 개수}) + \max\left(A_{i-1, k} \right), & \text{if } j\text{가 ①, ② 모두 만족} \end{cases} $$

1열부터 위 점화식을 계산해나가면 마지막 열에서 가능한 모든 자리들 중에서 최대값을 구하면 결국 총 앉을 수 있는 인원의 최대값을 구할 수 있게 되는 것이다.

비트 연산

한글로 풀어서 설명한 연산들도 비트연산으로 간단하게 해결할 수 있다.

  1. 현재 열 $j$에 부서진 자리가 앉는 학생이 없고, 붙어 앉는 학생이 없는 경우

    $i$열의 부서진 자리의 값을 case[i]라고 표현한다면

     j & case[i] == 0

    을 통해서 부서진 자리와 현재 상태 $j$가 겹치지 않을 경우 0이 나올 것으로 이를 통해 판단할 수 있다. 마찬가지로 옆자리에 다른 학생이 앉지 않는 경우는 비트시프트한 자기 자신과 AND 연산을 했을 때에 0 이외의 값이 나올 경우 옆자리에 붙어 앉아 있는 학생이 있다는 소리가 된다.

     (j & (j << 1)) == 0

  2. 현재열의 자리 $j$가 앞 열의 자리 $k$ 상태에서 컨닝이 불가능 한 경우

     mask = (k << 1) | (k >> 1)

    $k$의 대각선 방향, 즉 좌우만 없으면 없으면 되기 때문에 마스크를 오른쪽, 왼쪽 비트 시프트 후에 비트 OR 연산을 해주면 간단히 마스크를 만들 수 있고, 마찬가지로 mask와 j를 비트 AND 연산을 하여 0이 나오면, 조건을 만족, 0이외의 값이 나오면 대각선 자리에 앉는 학생이 있으므로 불만족하게 된다.

     j & mask == 0

코드

import sys
input = sys.stdin.readline

c = int(input())
for _ in range(c):
    n, m = list(map(int, input().replace('\n', '').split()))

    case = [0]
    for i in range(n):
        temp = '0b' + input().replace('\n', '').replace('x', '1').replace('.', '0')
        case.append(int(temp, 2))

    memo = [[0] * (2 ** m) for _ in range(n + 1)]

    for i in range(1, n+1):
        for j in range(2 ** m):
            if (j & (j << 1)) == 0 and j & case[i] == 0:
                # 좌우에 학생 없는 경우 + 부서진 자리에 앉지 않는 경우
                value = 0
                for k in range(2 ** m):
                    mask = (k << 1) | (k >> 1)
                    if (j & mask) == 0:
                        # 앞자리 학생을 컨닝하지 못하는 경우
                        if value < memo[i-1][k]:
                            value = memo[i-1][k]
                memo[i][j] = value + bin(j).count('1')
    
    print(max(memo[-1]))

숏코딩

숏코딩(혹은 code golf)는 주어진 문제를 최대한 짧은 코드로 해결하는 프로그래밍 스타일이다. 일반적으로 우리는 프로그래밍일 할 때, 가독성 및 유지보수성을 위해서 명확하고 간결한 코드를 작성하려고 한다. 그러나 숏코딩은 이와는 정반대로 오히려 가독성을 포기하고 길이를 최소화하는 것이 목표이다. 따라서 단순히 취미 이상으로 숏코딩에 집중하는 것은 크게 의미가 있어보이지 않고, 또 짧게 코드를 줄이는 과정에서 성능 저하가 발생할 수도 있고, 실무에서 협업시에는 말그대로 민폐가 될 수 있기 때문에 이런 것도 있다 정도로만 생각하면 좋을 것 같다. 다만 숏코딩의 방법을 참고하면 불필요하게 길게 작성되는 반복문 조건문 등을 줄이고, 또 코드의 작동 구조를 파악하는데에도 어느정도 도움이 되는 것 같다.

숏코딩에 주로 활용되는 언어로는 Perl, Python, Ruby, Golfscript, APL, J, PerL Golf 등이 있다고 한다. 다만, 오로지 짧은 코드를 만들겠다고 새로운 언어를 공부할 정도의 열정은 없었기 때문에 python 코드를 한번 극한으로 줄여보려고 한다.

숏코딩 풀이

비트 연산을 사용하면서 생각보다 코드 내용이 간단해지자, 갑자기 극한으로 줄일 수 있을 것 같다는 생각이 들었다. 위의 코드와 거의 동일한 알고리즘을 가지고 있지만, 극한으로 길이를 줄인다면 아래와 같은 형태의 코드를 얻을 수 있다. 글을 작성하는 시점에서의 본인도 해석하려면 힘든 수준의 암호로 변해버린 모습…

파이썬 코드를 줄이는 방법으로는 다음이 사용되었다.

  1. list 안에서 for문 사용
  2. 자주 쓰는 함수명 짧게 재정의
  3. indentation을 space 4칸에서 1칸으로
  4. 조건문을 boolean 값 직접 곱하는 것으로 치환
  5. for문, if문 이후 들여쓰기 x(1줄만 가능)
a,b,c,d=int,input,range,max
for _ in c(a(b())):
 n,m=list(map(a,b().split()))
 e=2**m
 s,M=[0]+[a(b().translate({120:49,46:48}),2)for _ in c(n)],[[0]*(e)]
 for i in c(1,n+1):M.append([d([M[i-1][k]*(j&(k<<1|k>>1)==0)for k in c(e)])+bin(j).count('1')*(j&j<<1==0)*(j&s[i]==0)for j in c(e)])
 print(d(M[-1]))

처음 제출이 1034B인 것에 반해서, 최종적으로는 무려 304B까지 줄일 수 있었다. 다만, 그 과정속에서 사용한 메모리는 크게 변화 없지만, 시간이 248ms에서 728ms로 거의 3배 가량 느려진 모습을 볼 수 있다. 따라서 숏코딩은 앞서 말한 것 처럼 한번 언어 구조를 파악하는 거 이상으로는 실질적인 도움은 되지 않을 것으로 보인다.