밝은 미래

관련글 http://luxs1t.tistory.com/238 처럼 깔끔하게 풀고 싶었는데,

괜히 쓸데 없는 생각까지 하다가 저질이 돼서 답이 안 나왔다.

언제 뒤짚을까를 얼렁뚱땅 이상한 수식으로 때려맞추려고 했다.

            substract = n % (pow(10, i+1)) - 1            r = reverse(n - substract)
            if r + substract + 1 < next_n + next_s and r >= 0:

그냥 정직하게 언제 뒤짚는게 좋을지를 생각해보면 좋았을텐데.

자릿수를 맞춘 다음에 최종 숫자에 도달하는 것도 착실하게 다 체크하는 것이 좋았다.

import math

sample = "sample"
small = "A-small-attempt3"
large = "A-large"
current = sample

fin = open(current + ".in", "r")
fout = open(current + ".out", 'w')
# f1out = open(current + "1.out", 'w')
# f2out = open(current + "2.out", 'w')

T = int(fin.readline())

def reverse(n):
    result = 0
    while n:
        digit = n % 10
        n = n / 10
        result = result * 10 + digit
    return result

def solve(N):
    n = N
    times = 0

    while n:
        next_n = n-1
        next_s = 1
        for i in range(len(str(n))-1):
            substract = n % (pow(10, i+1)) - 1
            r = reverse(n - substract)
            if r + substract + 1 < next_n + next_s and r >= 0:
                #print "   ", n, next_n, r
                next_n = r
                next_s = substract + 1
        if next_s > 1:
            print n, next_n, next_s
        times += next_s
        n = next_n
        # if n > r #and (n % 10 != 0) and (n % 10 == 1):
        #     print n, r
        #     n = r
        # else:
        #     n -= 1

    return str(times)

# def bottomup(N):
#     p = 0
#     while p != n:
#         next_i = p+1
#         next_a = 1
#         for i in range(len(str(N))-1):
#             adding =

def less(N, n, times):
    if n <= 0:
        return times
    if times > N:
        return times
    r = reverse(n)
    times1 = less(N, n-1, times+1)
    times2 = less(N, r-1, times+2)
    return min(times1, times2)

def brute(N):

    return str(less(N, N-1, 1))

for i in range(T):
    N = int(fin.readline())
    print N
    solution = solve(N)
    # b_solution = brute(N)
    # if solution != b_solution:
    #     print solution, b_solution
    answer = "Case #%d: %s\n" % (i + 1, solution)
    print answer
    fout.write(answer)

fin.close()
fout.close()
# f1out.close()
# f2out.close()

결국, 코드도 못 적었다.

내가 생각한 풀이 방법은

hikers의 시간/변위 그래프를 그려 보고,

그 선들을 최소로 지나면서, 왼쪽 아래에서 오른쪽 위로 향하는 곡선을 만들기

였는데, track이 원이고, 각 hiker가 몇 번 track을 돌 지 모르기 때문에 더 어려웠다.

꽤 잘 생각한 idea라고 생각했었는데,

해답을 보니, 이런 풀이 방법이 아니네... T_T

52 people successfully solved the large input for this problem