골드 러시 10275

44 minute read

문제

골드 러시 을 풀어 보았습니다.

문제에 접근하기

다음의 사실들을 인지하고 넘어가야 할 필요가 있습니다.

가방 a 혹은 b 중 큰 가방에만(혹은 작은 가방에만) 금을 꽉 채워 넣으면 다른 가방에는 자동으로 금이 꽉 찹니다. a + b = 2**n 이기 때문입니다. 따라서 저는 a 와 b 중 큰 가방의 용량을 취해서 계산에 사용합니다. 작은 가방의 용량은 생각하지 않습니다.
a, b >= 1 이기 때문에 첫 날에 큰 가방에 금이 다 들어가는 일은 없습니다. 마법은 무조건 한 번 이상 사용해야 합니다.
마법은 금이 1 펨토그램이 될 때 까지 금을 절반으로 나눌 수 있습니다. x가 금의 무게라고 하고 날마다 쪼개는 금 조각의 무게를 수열로 나타내면 [x//2, x//2//2, x//2//2//2 ...] 입니다. 예를 들어 금의 무게가 64 라고 하면 [32, 16, 8, 4, 2, 1, 0] 입니다.
위 수열에서 0 번째 요소 > 그 이후의 모든 요소의 합 입니다. 예를 들어 32 > 16, 8, 4, 2, 1 0 의 합 입니다.

input 받기

먼저 각 case의 input 을 받아 봅니다.

case_cnt = int(input())
case_list = []
for i in range(0, case_cnt):
    case_list.append(input().split(' '))

for case in case_list:
    answer(case)

공백을 기준으로 자르고, 정수값은 int() 를 사용해 integer 로 바꿔줍니다. 각 case 마다 case 의 답을 출력하는 함수 answer 를 호출해 줍니다. answer 함수의 내용은 밑에서 설명합니다.

memo

다이나믹 프로그래밍 문제를 해결할 때에는 계산 결과를 저장해 두는 것이 중요합니다. 계산 결과를 저장&불러오기를 하지 않고 값이 필요할 때마다 일일이 계산한다면 시간 초과를 면치 못합니다.

좀 야비하다고 생각할지도 모르겠지만, 그리고 테스트 케이스의 수에 따라서 오히려 시간을 더 잡아먹는 방법일지도 모르지만 n이 최대 62 까지 있으므로 1부터 62의 모든 n에 대해 계산된 값을 딕셔너리 memo 에 저장합니다.

memo = {0: [0], 1: [1, 0], 2: [2, 1, 0], 3: [4, 2, 1, 0], 4: [8, 4, 2, 1, 0], 5: [16, 8, 4, 2, 1, 0],
        6: [32, 16, 8, 4, 2, 1, 0], 7: [64, 32, 16, 8, 4, 2, 1, 0], 8: [128, 64, 32, 16, 8, 4, 2, 1, 0],
        9: [256, 128, 64, 32, 16, 8, 4, 2, 1, 0], 10: [512, 256, 128, 64, 32, 16, 8, 4, 2, 1, 0],
        11: [1024, 512, 256, 128, 64, 32, 16, 8, 4, 2, 1, 0],
        12: [2048, 1024, 512, 256, 128, 64, 32, 16, 8, 4, 2, 1, 0],
        13: [4096, 2048, 1024, 512, 256, 128, 64, 32, 16, 8, 4, 2, 1, 0],
        14: [8192, 4096, 2048, 1024, 512, 256, 128, 64, 32, 16, 8, 4, 2, 1, 0],
        15: [16384, 8192, 4096, 2048, 1024, 512, 256, 128, 64, 32, 16, 8, 4, 2, 1, 0],
        16: [32768, 16384, 8192, 4096, 2048, 1024, 512, 256, 128, 64, 32, 16, 8, 4, 2, 1, 0],
        17: [65536, 32768, 16384, 8192, 4096, 2048, 1024, 512, 256, 128, 64, 32, 16, 8, 4, 2, 1, 0],
        18: [131072, 65536, 32768, 16384, 8192, 4096, 2048, 1024, 512, 256, 128, 64, 32, 16, 8, 4, 2, 1, 0],
        19: [262144, 131072, 65536, 32768, 16384, 8192, 4096, 2048, 1024, 512, 256, 128, 64, 32, 16, 8, 4, 2, 1, 0],
        20: [524288, 262144, 131072, 65536, 32768, 16384, 8192, 4096, 2048, 1024, 512, 256, 128, 64, 32, 16, 8, 4, 2, 1,
             0],
        21: [1048576, 524288, 262144, 131072, 65536, 32768, 16384, 8192, 4096, 2048, 1024, 512, 256, 128, 64, 32, 16, 8,
             4, 2, 1, 0],
        22: [2097152, 1048576, 524288, 262144, 131072, 65536, 32768, 16384, 8192, 4096, 2048, 1024, 512, 256, 128, 64,
             32, 16, 8, 4, 2, 1, 0],
        23: [4194304, 2097152, 1048576, 524288, 262144, 131072, 65536, 32768, 16384, 8192, 4096, 2048, 1024, 512, 256,
             128, 64, 32, 16, 8, 4, 2, 1, 0],
        24: [8388608, 4194304, 2097152, 1048576, 524288, 262144, 131072, 65536, 32768, 16384, 8192, 4096, 2048, 1024,
             512, 256, 128, 64, 32, 16, 8, 4, 2, 1, 0],
        25: [16777216, 8388608, 4194304, 2097152, 1048576, 524288, 262144, 131072, 65536, 32768, 16384, 8192, 4096,
             2048, 1024, 512, 256, 128, 64, 32, 16, 8, 4, 2, 1, 0],
        26: [33554432, 16777216, 8388608, 4194304, 2097152, 1048576, 524288, 262144, 131072, 65536, 32768, 16384, 8192,
             4096, 2048, 1024, 512, 256, 128, 64, 32, 16, 8, 4, 2, 1, 0],
        27: [67108864, 33554432, 16777216, 8388608, 4194304, 2097152, 1048576, 524288, 262144, 131072, 65536, 32768,
             16384, 8192, 4096, 2048, 1024, 512, 256, 128, 64, 32, 16, 8, 4, 2, 1, 0],
        28: [134217728, 67108864, 33554432, 16777216, 8388608, 4194304, 2097152, 1048576, 524288, 262144, 131072, 65536,
             32768, 16384, 8192, 4096, 2048, 1024, 512, 256, 128, 64, 32, 16, 8, 4, 2, 1, 0],
        29: [268435456, 134217728, 67108864, 33554432, 16777216, 8388608, 4194304, 2097152, 1048576, 524288, 262144,
             131072, 65536, 32768, 16384, 8192, 4096, 2048, 1024, 512, 256, 128, 64, 32, 16, 8, 4, 2, 1, 0],
        30: [536870912, 268435456, 134217728, 67108864, 33554432, 16777216, 8388608, 4194304, 2097152, 1048576, 524288,
             262144, 131072, 65536, 32768, 16384, 8192, 4096, 2048, 1024, 512, 256, 128, 64, 32, 16, 8, 4, 2, 1, 0],
        31: [1073741824, 536870912, 268435456, 134217728, 67108864, 33554432, 16777216, 8388608, 4194304, 2097152,
             1048576, 524288, 262144, 131072, 65536, 32768, 16384, 8192, 4096, 2048, 1024, 512, 256, 128, 64, 32, 16, 8,
             4, 2, 1, 0],
        32: [2147483648, 1073741824, 536870912, 268435456, 134217728, 67108864, 33554432, 16777216, 8388608, 4194304,
             2097152, 1048576, 524288, 262144, 131072, 65536, 32768, 16384, 8192, 4096, 2048, 1024, 512, 256, 128, 64,
             32, 16, 8, 4, 2, 1, 0],
        33: [4294967296, 2147483648, 1073741824, 536870912, 268435456, 134217728, 67108864, 33554432, 16777216, 8388608,
             4194304, 2097152, 1048576, 524288, 262144, 131072, 65536, 32768, 16384, 8192, 4096, 2048, 1024, 512, 256,
             128, 64, 32, 16, 8, 4, 2, 1, 0],
        34: [8589934592, 4294967296, 2147483648, 1073741824, 536870912, 268435456, 134217728, 67108864, 33554432,
             16777216, 8388608, 4194304, 2097152, 1048576, 524288, 262144, 131072, 65536, 32768, 16384, 8192, 4096,
             2048, 1024, 512, 256, 128, 64, 32, 16, 8, 4, 2, 1, 0],
        35: [17179869184, 8589934592, 4294967296, 2147483648, 1073741824, 536870912, 268435456, 134217728, 67108864,
             33554432, 16777216, 8388608, 4194304, 2097152, 1048576, 524288, 262144, 131072, 65536, 32768, 16384, 8192,
             4096, 2048, 1024, 512, 256, 128, 64, 32, 16, 8, 4, 2, 1, 0],
        36: [34359738368, 17179869184, 8589934592, 4294967296, 2147483648, 1073741824, 536870912, 268435456, 134217728,
             67108864, 33554432, 16777216, 8388608, 4194304, 2097152, 1048576, 524288, 262144, 131072, 65536, 32768,
             16384, 8192, 4096, 2048, 1024, 512, 256, 128, 64, 32, 16, 8, 4, 2, 1, 0],
        37: [68719476736, 34359738368, 17179869184, 8589934592, 4294967296, 2147483648, 1073741824, 536870912,
             268435456, 134217728, 67108864, 33554432, 16777216, 8388608, 4194304, 2097152, 1048576, 524288, 262144,
             131072, 65536, 32768, 16384, 8192, 4096, 2048, 1024, 512, 256, 128, 64, 32, 16, 8, 4, 2, 1, 0],
        38: [137438953472, 68719476736, 34359738368, 17179869184, 8589934592, 4294967296, 2147483648, 1073741824,
             536870912, 268435456, 134217728, 67108864, 33554432, 16777216, 8388608, 4194304, 2097152, 1048576, 524288,
             262144, 131072, 65536, 32768, 16384, 8192, 4096, 2048, 1024, 512, 256, 128, 64, 32, 16, 8, 4, 2, 1, 0],
        39: [274877906944, 137438953472, 68719476736, 34359738368, 17179869184, 8589934592, 4294967296, 2147483648,
             1073741824, 536870912, 268435456, 134217728, 67108864, 33554432, 16777216, 8388608, 4194304, 2097152,
             1048576, 524288, 262144, 131072, 65536, 32768, 16384, 8192, 4096, 2048, 1024, 512, 256, 128, 64, 32, 16, 8,
             4, 2, 1, 0],
        40: [549755813888, 274877906944, 137438953472, 68719476736, 34359738368, 17179869184, 8589934592, 4294967296,
             2147483648, 1073741824, 536870912, 268435456, 134217728, 67108864, 33554432, 16777216, 8388608, 4194304,
             2097152, 1048576, 524288, 262144, 131072, 65536, 32768, 16384, 8192, 4096, 2048, 1024, 512, 256, 128, 64,
             32, 16, 8, 4, 2, 1, 0],
        41: [1099511627776, 549755813888, 274877906944, 137438953472, 68719476736, 34359738368, 17179869184, 8589934592,
             4294967296, 2147483648, 1073741824, 536870912, 268435456, 134217728, 67108864, 33554432, 16777216, 8388608,
             4194304, 2097152, 1048576, 524288, 262144, 131072, 65536, 32768, 16384, 8192, 4096, 2048, 1024, 512, 256,
             128, 64, 32, 16, 8, 4, 2, 1, 0],
        42: [2199023255552, 1099511627776, 549755813888, 274877906944, 137438953472, 68719476736, 34359738368,
             17179869184, 8589934592, 4294967296, 2147483648, 1073741824, 536870912, 268435456, 134217728, 67108864,
             33554432, 16777216, 8388608, 4194304, 2097152, 1048576, 524288, 262144, 131072, 65536, 32768, 16384, 8192,
             4096, 2048, 1024, 512, 256, 128, 64, 32, 16, 8, 4, 2, 1, 0],
        43: [4398046511104, 2199023255552, 1099511627776, 549755813888, 274877906944, 137438953472, 68719476736,
             34359738368, 17179869184, 8589934592, 4294967296, 2147483648, 1073741824, 536870912, 268435456, 134217728,
             67108864, 33554432, 16777216, 8388608, 4194304, 2097152, 1048576, 524288, 262144, 131072, 65536, 32768,
             16384, 8192, 4096, 2048, 1024, 512, 256, 128, 64, 32, 16, 8, 4, 2, 1, 0],
        44: [8796093022208, 4398046511104, 2199023255552, 1099511627776, 549755813888, 274877906944, 137438953472,
             68719476736, 34359738368, 17179869184, 8589934592, 4294967296, 2147483648, 1073741824, 536870912,
             268435456, 134217728, 67108864, 33554432, 16777216, 8388608, 4194304, 2097152, 1048576, 524288, 262144,
             131072, 65536, 32768, 16384, 8192, 4096, 2048, 1024, 512, 256, 128, 64, 32, 16, 8, 4, 2, 1, 0],
        45: [17592186044416, 8796093022208, 4398046511104, 2199023255552, 1099511627776, 549755813888, 274877906944,
             137438953472, 68719476736, 34359738368, 17179869184, 8589934592, 4294967296, 2147483648, 1073741824,
             536870912, 268435456, 134217728, 67108864, 33554432, 16777216, 8388608, 4194304, 2097152, 1048576, 524288,
             262144, 131072, 65536, 32768, 16384, 8192, 4096, 2048, 1024, 512, 256, 128, 64, 32, 16, 8, 4, 2, 1, 0],
        46: [35184372088832, 17592186044416, 8796093022208, 4398046511104, 2199023255552, 1099511627776, 549755813888,
             274877906944, 137438953472, 68719476736, 34359738368, 17179869184, 8589934592, 4294967296, 2147483648,
             1073741824, 536870912, 268435456, 134217728, 67108864, 33554432, 16777216, 8388608, 4194304, 2097152,
             1048576, 524288, 262144, 131072, 65536, 32768, 16384, 8192, 4096, 2048, 1024, 512, 256, 128, 64, 32, 16, 8,
             4, 2, 1, 0],
        47: [70368744177664, 35184372088832, 17592186044416, 8796093022208, 4398046511104, 2199023255552, 1099511627776,
             549755813888, 274877906944, 137438953472, 68719476736, 34359738368, 17179869184, 8589934592, 4294967296,
             2147483648, 1073741824, 536870912, 268435456, 134217728, 67108864, 33554432, 16777216, 8388608, 4194304,
             2097152, 1048576, 524288, 262144, 131072, 65536, 32768, 16384, 8192, 4096, 2048, 1024, 512, 256, 128, 64,
             32, 16, 8, 4, 2, 1, 0],
        48: [140737488355328, 70368744177664, 35184372088832, 17592186044416, 8796093022208, 4398046511104,
             2199023255552, 1099511627776, 549755813888, 274877906944, 137438953472, 68719476736, 34359738368,
             17179869184, 8589934592, 4294967296, 2147483648, 1073741824, 536870912, 268435456, 134217728, 67108864,
             33554432, 16777216, 8388608, 4194304, 2097152, 1048576, 524288, 262144, 131072, 65536, 32768, 16384, 8192,
             4096, 2048, 1024, 512, 256, 128, 64, 32, 16, 8, 4, 2, 1, 0],
        49: [281474976710656, 140737488355328, 70368744177664, 35184372088832, 17592186044416, 8796093022208,
             4398046511104, 2199023255552, 1099511627776, 549755813888, 274877906944, 137438953472, 68719476736,
             34359738368, 17179869184, 8589934592, 4294967296, 2147483648, 1073741824, 536870912, 268435456, 134217728,
             67108864, 33554432, 16777216, 8388608, 4194304, 2097152, 1048576, 524288, 262144, 131072, 65536, 32768,
             16384, 8192, 4096, 2048, 1024, 512, 256, 128, 64, 32, 16, 8, 4, 2, 1, 0],
        50: [562949953421312, 281474976710656, 140737488355328, 70368744177664, 35184372088832, 17592186044416,
             8796093022208, 4398046511104, 2199023255552, 1099511627776, 549755813888, 274877906944, 137438953472,
             68719476736, 34359738368, 17179869184, 8589934592, 4294967296, 2147483648, 1073741824, 536870912,
             268435456, 134217728, 67108864, 33554432, 16777216, 8388608, 4194304, 2097152, 1048576, 524288, 262144,
             131072, 65536, 32768, 16384, 8192, 4096, 2048, 1024, 512, 256, 128, 64, 32, 16, 8, 4, 2, 1, 0],
        51: [1125899906842624, 562949953421312, 281474976710656, 140737488355328, 70368744177664, 35184372088832,
             17592186044416, 8796093022208, 4398046511104, 2199023255552, 1099511627776, 549755813888, 274877906944,
             137438953472, 68719476736, 34359738368, 17179869184, 8589934592, 4294967296, 2147483648, 1073741824,
             536870912, 268435456, 134217728, 67108864, 33554432, 16777216, 8388608, 4194304, 2097152, 1048576, 524288,
             262144, 131072, 65536, 32768, 16384, 8192, 4096, 2048, 1024, 512, 256, 128, 64, 32, 16, 8, 4, 2, 1, 0],
        52: [2251799813685248, 1125899906842624, 562949953421312, 281474976710656, 140737488355328, 70368744177664,
             35184372088832, 17592186044416, 8796093022208, 4398046511104, 2199023255552, 1099511627776, 549755813888,
             274877906944, 137438953472, 68719476736, 34359738368, 17179869184, 8589934592, 4294967296, 2147483648,
             1073741824, 536870912, 268435456, 134217728, 67108864, 33554432, 16777216, 8388608, 4194304, 2097152,
             1048576, 524288, 262144, 131072, 65536, 32768, 16384, 8192, 4096, 2048, 1024, 512, 256, 128, 64, 32, 16, 8,
             4, 2, 1, 0],
        53: [4503599627370496, 2251799813685248, 1125899906842624, 562949953421312, 281474976710656, 140737488355328,
             70368744177664, 35184372088832, 17592186044416, 8796093022208, 4398046511104, 2199023255552, 1099511627776,
             549755813888, 274877906944, 137438953472, 68719476736, 34359738368, 17179869184, 8589934592, 4294967296,
             2147483648, 1073741824, 536870912, 268435456, 134217728, 67108864, 33554432, 16777216, 8388608, 4194304,
             2097152, 1048576, 524288, 262144, 131072, 65536, 32768, 16384, 8192, 4096, 2048, 1024, 512, 256, 128, 64,
             32, 16, 8, 4, 2, 1, 0],
        54: [9007199254740992, 4503599627370496, 2251799813685248, 1125899906842624, 562949953421312, 281474976710656,
             140737488355328, 70368744177664, 35184372088832, 17592186044416, 8796093022208, 4398046511104,
             2199023255552, 1099511627776, 549755813888, 274877906944, 137438953472, 68719476736, 34359738368,
             17179869184, 8589934592, 4294967296, 2147483648, 1073741824, 536870912, 268435456, 134217728, 67108864,
             33554432, 16777216, 8388608, 4194304, 2097152, 1048576, 524288, 262144, 131072, 65536, 32768, 16384, 8192,
             4096, 2048, 1024, 512, 256, 128, 64, 32, 16, 8, 4, 2, 1, 0],
        55: [18014398509481984, 9007199254740992, 4503599627370496, 2251799813685248, 1125899906842624, 562949953421312,
             281474976710656, 140737488355328, 70368744177664, 35184372088832, 17592186044416, 8796093022208,
             4398046511104, 2199023255552, 1099511627776, 549755813888, 274877906944, 137438953472, 68719476736,
             34359738368, 17179869184, 8589934592, 4294967296, 2147483648, 1073741824, 536870912, 268435456, 134217728,
             67108864, 33554432, 16777216, 8388608, 4194304, 2097152, 1048576, 524288, 262144, 131072, 65536, 32768,
             16384, 8192, 4096, 2048, 1024, 512, 256, 128, 64, 32, 16, 8, 4, 2, 1, 0],
        56: [36028797018963968, 18014398509481984, 9007199254740992, 4503599627370496, 2251799813685248,
             1125899906842624, 562949953421312, 281474976710656, 140737488355328, 70368744177664, 35184372088832,
             17592186044416, 8796093022208, 4398046511104, 2199023255552, 1099511627776, 549755813888, 274877906944,
             137438953472, 68719476736, 34359738368, 17179869184, 8589934592, 4294967296, 2147483648, 1073741824,
             536870912, 268435456, 134217728, 67108864, 33554432, 16777216, 8388608, 4194304, 2097152, 1048576, 524288,
             262144, 131072, 65536, 32768, 16384, 8192, 4096, 2048, 1024, 512, 256, 128, 64, 32, 16, 8, 4, 2, 1, 0],
        57: [72057594037927936, 36028797018963968, 18014398509481984, 9007199254740992, 4503599627370496,
             2251799813685248, 1125899906842624, 562949953421312, 281474976710656, 140737488355328, 70368744177664,
             35184372088832, 17592186044416, 8796093022208, 4398046511104, 2199023255552, 1099511627776, 549755813888,
             274877906944, 137438953472, 68719476736, 34359738368, 17179869184, 8589934592, 4294967296, 2147483648,
             1073741824, 536870912, 268435456, 134217728, 67108864, 33554432, 16777216, 8388608, 4194304, 2097152,
             1048576, 524288, 262144, 131072, 65536, 32768, 16384, 8192, 4096, 2048, 1024, 512, 256, 128, 64, 32, 16, 8,
             4, 2, 1, 0],
        58: [144115188075855872, 72057594037927936, 36028797018963968, 18014398509481984, 9007199254740992,
             4503599627370496, 2251799813685248, 1125899906842624, 562949953421312, 281474976710656, 140737488355328,
             70368744177664, 35184372088832, 17592186044416, 8796093022208, 4398046511104, 2199023255552, 1099511627776,
             549755813888, 274877906944, 137438953472, 68719476736, 34359738368, 17179869184, 8589934592, 4294967296,
             2147483648, 1073741824, 536870912, 268435456, 134217728, 67108864, 33554432, 16777216, 8388608, 4194304,
             2097152, 1048576, 524288, 262144, 131072, 65536, 32768, 16384, 8192, 4096, 2048, 1024, 512, 256, 128, 64,
             32, 16, 8, 4, 2, 1, 0],
        59: [288230376151711744, 144115188075855872, 72057594037927936, 36028797018963968, 18014398509481984,
             9007199254740992, 4503599627370496, 2251799813685248, 1125899906842624, 562949953421312, 281474976710656,
             140737488355328, 70368744177664, 35184372088832, 17592186044416, 8796093022208, 4398046511104,
             2199023255552, 1099511627776, 549755813888, 274877906944, 137438953472, 68719476736, 34359738368,
             17179869184, 8589934592, 4294967296, 2147483648, 1073741824, 536870912, 268435456, 134217728, 67108864,
             33554432, 16777216, 8388608, 4194304, 2097152, 1048576, 524288, 262144, 131072, 65536, 32768, 16384, 8192,
             4096, 2048, 1024, 512, 256, 128, 64, 32, 16, 8, 4, 2, 1, 0],
        60: [576460752303423488, 288230376151711744, 144115188075855872, 72057594037927936, 36028797018963968,
             18014398509481984, 9007199254740992, 4503599627370496, 2251799813685248, 1125899906842624, 562949953421312,
             281474976710656, 140737488355328, 70368744177664, 35184372088832, 17592186044416, 8796093022208,
             4398046511104, 2199023255552, 1099511627776, 549755813888, 274877906944, 137438953472, 68719476736,
             34359738368, 17179869184, 8589934592, 4294967296, 2147483648, 1073741824, 536870912, 268435456, 134217728,
             67108864, 33554432, 16777216, 8388608, 4194304, 2097152, 1048576, 524288, 262144, 131072, 65536, 32768,
             16384, 8192, 4096, 2048, 1024, 512, 256, 128, 64, 32, 16, 8, 4, 2, 1, 0],
        61: [1152921504606846976, 576460752303423488, 288230376151711744, 144115188075855872, 72057594037927936,
             36028797018963968, 18014398509481984, 9007199254740992, 4503599627370496, 2251799813685248,
             1125899906842624, 562949953421312, 281474976710656, 140737488355328, 70368744177664, 35184372088832,
             17592186044416, 8796093022208, 4398046511104, 2199023255552, 1099511627776, 549755813888, 274877906944,
             137438953472, 68719476736, 34359738368, 17179869184, 8589934592, 4294967296, 2147483648, 1073741824,
             536870912, 268435456, 134217728, 67108864, 33554432, 16777216, 8388608, 4194304, 2097152, 1048576, 524288,
             262144, 131072, 65536, 32768, 16384, 8192, 4096, 2048, 1024, 512, 256, 128, 64, 32, 16, 8, 4, 2, 1, 0],
        62: [2305843009213693952, 1152921504606846976, 576460752303423488, 288230376151711744, 144115188075855872,
             72057594037927936, 36028797018963968, 18014398509481984, 9007199254740992, 4503599627370496,
             2251799813685248, 1125899906842624, 562949953421312, 281474976710656, 140737488355328, 70368744177664,
             35184372088832, 17592186044416, 8796093022208, 4398046511104, 2199023255552, 1099511627776, 549755813888,
             274877906944, 137438953472, 68719476736, 34359738368, 17179869184, 8589934592, 4294967296, 2147483648,
             1073741824, 536870912, 268435456, 134217728, 67108864, 33554432, 16777216, 8388608, 4194304, 2097152,
             1048576, 524288, 262144, 131072, 65536, 32768, 16384, 8192, 4096, 2048, 1024, 512, 256, 128, 64, 32, 16, 8,
             4, 2, 1, 0]
        }

이걸 다 손으로 쳤을리가 없죠. memo 를 만드는데에도 파이썬을 사용합니다. 파이썬 콘솔을 열어서 함수 하나를 정의 한 후, 딕셔너리 컴프리헨션으로 만들었습니다.

def get_sliced(n):
    weight = 2 ** n
    sliced = []
    while True:
        if weight == 0: # weight 가 0이 될 일은 없긴 하지만...
            break
        weight = weight // 2
        sliced.append(weight)
    return sliced

{n : get_sliced(n) for n in range(63)} # memo 생성

answer 함수 작성

def answer(case):
    n, a, b = int(case[0]), int(case[1]), int(case[2])
    big_bag_limit = a if a > b else b
    day=1
    cur_big_bag = 0
    # 나누지 않고 가방 하나에 다 들어가는 경우는 없다. a, b >= 1

    while True:
        cur_big_bag += memo[n][day-1]

        if cur_big_bag > big_bag_limit:
            # 만약 가방의 크기보다 금을 더 많이 넣었다면, 오늘의 조각은 가방에서 뺀다.
            cur_big_bag -= memo[n][day-1]

        if cur_big_bag == big_bag_limit:
            print(day)
            return

        # cur_big_bag < big_bag_limit: pass # 그냥 넘어가면 된다.

        day += 1 # 하루가 지난다.

중요한 포인트는, 오늘의 조각 (memo[n][day-1]) 을 가방에 넣었을때 가방이 넘친다면, 오늘의 조각은 가방에서 뺀다(버린다)는 것이에요.

예제 케이스 10 1000 24 를 가지고 설명하겠습니다.

memo[10] 은 다음과 같습니다.

10: [512, 256, 128, 64, 32, 16, 8, 4, 2, 1, 0]

큰 가방인 1000에 금을 꽉 채우려면 다음의 숫자가 필요합니다.

sum([512, 256, 128, 64, 32, 8]) == 1000

즉, 16은 넣을 수 없습니다! 만약 16 을 넣게 되면…

sum([512, 256, 128, 64, 32, 16]) == 1008
sum([512, 256, 128, 64, 32, 16, 8]) == 1016

가방이 넘치게 됩니다. 그리고 계속해서 큰 가방에 금을 넣어가는 구조상, 1000을 넘는 순간 부터 더 이상 답을 찾을 수 없게 됩니다. 그래서 현재 가방의 용량이 넘쳤는지 넘치지 않았는지 체크하는 if 문이 필요합니다.

if cur_big_bag > big_bag_limit:
    # 만약 가방의 크기보다 금을 더 많이 넣었다면, 오늘의 조각은 가방에서 뺀다.
    cur_big_bag -= memo[n][day-1]

최종적으로는, 가방의 꽉 차게 되었을 때 여태까지 소요된 일수(day)를 출력하고 함수를 빠져나오면 됩니다.

if cur_big_bag == big_bag_limit:
    print(day)
    return

Twitter Facebook LinkedIn

정승원

골드 러시 10275

문제

문제에 접근하기

input 받기

memo

answer 함수 작성

Comments

You May Also Enjoy

곰보일기

(전자책) onyx boox note3 리뷰

python 디렉터리 안의 모든 영상 길이 sum 하기

TIL: JAVA