[BOJ 3996] 위대한 사기꾼

1) 문제 링크

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

2) 접근

몇 번 끄적이다 보니… 구간 $[0, n]$에 속한 자연수 중 k진법으로 표현했을 때 뒤에서 2, 4, 6, …번째에 있는 자릿수가 모두 0인 것이 ‘k진법 = -k진법’의 필요충분조건임을 깨달았다. 그리고, n을 k*k진법으로 바꾸면 이를 만족하는 자연수의 개수를 바로 계산할 수 있을 것이라 생각했다.

3) 풀이

n, k = map(int, input().split())
k_sq_based_n = list()

while n:
    k_sq_based_n.insert(0, n%(k*k))
    n //= k*k

res = 0
for digit in k_sq_based_n:
    if digit >= (k-1):
        res += k-1
    else:
        res += digit
    res *= k

res //= k
res += 1
print(res)

처음으로 짠 코드인데… 예제 입력도 잘 맞아떨어지고 최소 입력(n=1, k=2 등)에 대해서도 잘 작동했다. 맞왜틀?
이후 몇 가지 입력을 더 넣어보던 중 27을 넣었을 때 9가 아니라 7이 나오는 것을 보았다. 코드를 가만히 살펴보다가 if digit >= (k-1)이 아니라 digit >= k로 빼줬어야 함을 깨달았다. digit > (k-1)이 더 깔끔하려나? 암튼.

n, k = map(int, input().split())
k_sq_based_n = list()

while n:
    k_sq_based_n.insert(0, n%(k*k))
    n //= k*k

res = 0
flag = 0 # k진법의 자릿수를 초과하는 자릿수가 있는지 검사. 있다면 1.
for digit in k_sq_based_n:
    if digit >= k:
        res += k
        flag = 1
    elif flag == 0:
        res += digit
    res *= k

res //= k
if(flag == 0):
    res += 1
print(res)

???????????????????????
알고 보니 flag의 위치가 틀렸던 거였다. 애초에 flag 올라갔으면 그 뒤 자릿수들을 고려하면 안 되는데 쓸데없이 고려해서 셌으니…

n, k = map(int, input().split())
k_sq_based_n = list()

while n:
    k_sq_based_n.insert(0, n%(k*k))
    n //= k*k

res = 0
flag = 0
for digit in k_sq_based_n:
    if flag == 0:
        if digit >= k:
            res += k
            flag = 1
        else:
            res += digit
    res *= k

res //= k
if(flag == 0):
    res += 1
print(res)

겨우 맞았네 ㅋㅋ

4) 피드백

다 풀고 찜찜한 느낌이 들었다. flag를 안 쓰고 푸는 법은 없을까?