[백준] 10448 : 유레카 이론 (Python)

문제 링크 : https://www.acmicpc.net/problem/10448

풀이 코드

---

num_cases = int(input())

vals = []
for i in range(num_cases):
    vals.append(int(input()))

res = []
T_list = [1]
for i in range(1,45,1):
    T_list.append(T_list[i-1]+i+1)

reverse_idx = range(44, -1, -1)

for val in vals:
    result=0

    for idx_i, i in enumerate(reverse_idx):
        if val - T_list[i] < 0 :
            continue
        val -= T_list[i]
        for idx_j, j in enumerate(reverse_idx[idx_i:]):
            if val - T_list[j] < 0 :
                continue
            val -= T_list[j]
            for idx_k, k in enumerate(reverse_idx[idx_j:]):
                if val - T_list[k] < 0 :
                    continue
                val -= T_list[k]

                if val == 0 :
                    result=1

                if result:
                    break
                val += T_list[k]
            if result:
                break
            val += T_list[j]
        if result:
            break
        val += T_list[i]

    res.append(result)

for c in range(num_cases):
    print(res[c])

풀이 해설

---

입력되는 수 K의 범위가 1000까지 이기 때문에 최대 T값은 1000을 넘을 수 없어 최대 44개의 T가 생성됩니다

입력된 숫자에 대해 계속해서 T를 계산해줄 경우 케이스가 늘어남에 따라 상당히 많은 시간이 소요되기 때문에
한 번 T를 만들어 둔 뒤 조합을 생각할 때 사용만 하도록 합니다

위 풀이에서는 입력된 K에 따라 계속해서 조합이 가능한지 체크를 하고 있지만
1000 이하로 가능한 조합에 대해 미리 테이블을 만들어 둔다면 추가적으로 시간을 감소시킬 수 있습니다