[BOJ][Python]10157번 풀이

https://www.acmicpc.net/problem/10157

10157번: 자리배정

c,r = map(int, input().split())
k = int(input())
s = 0
shell = [0]
while 1:
    a = ((c-1-2*s)+(r-1-2*s))*2
    if a > 0:
        shell.append(a + shell[-1])
        s += 1
    else:
        break
if c*r < k :
    print(0)
else:
    r_start = 0
    c_start = 0
    for i in range(1, len(shell)):
        if k <= shell[i]:
            k -= shell[i-1]
            r_start, c_start = i-1, i-1
            c = c-2*(i-1)
            r = r-2*(i-1)
            break
    if k <= r:
        print(1 + c_start, r_start + k)#1
    elif k < r+c:
        print(1 + c_start - r + k, r_start + r)#2
    elif k < 2*r + c - 1:
        print(c_start + c, r_start + r - 1 - (k - r - c))#3
    else:
        print(c_start + c - 2 - (k - 2*r - c), r_start + 1)#4
'''
1 : increase r
2 : increase c
3 : decrease r
4 : decrease c
'''

구현 문제는 항상 표기 난이도에 비해 생각하는 시간이 많이 필요한 것 같습니다. 보자마자 방법은 떠오르는데 이걸 어떻게 코드로 옮길지 고민을 하다보면 어느새 시간이 훌쩍 지나있어요. 거기다 어줍잖게 아는 경우 효율적인 방법이 뭔지를 고민하다 더 시간을 날리는 경우도 있구요. O(n^2)이든 O(n^3)이든 돌아가도록만 만들어놓고 최적화를 시켜도 되는데 말이죠.

 

문제의 접근은 대기번호에 따른 좌석이 맨 바깥 좌석부터 해서 시계방향으로 돌면서 배정이 된다는 점인데, 둘 중에 하나는 고정된 채로 움직인다는 점이 주의할 점이겠습니다. 따라서 저는 4가지 경우로 나눠서 조건문을 작성했습니다. 다만 막상 풀고 나니까 위에 있는 shell은 필요가 없는 부분이었다는게 느껴지네요. 그냥 메인에 있는 for 반복문 안에서 k에 대한 i를 추출하면서 동시에 처리가 가능했던 부분이라고 생각이 됩니다. 디버깅할 때는 편했지만요.