[BOJ] 백준 알고리즘 9095번 정답 코드

# 1, 2, 3 더하기
 
class Counter(object):
    save = None
 
    def init_save(self, N):
        if N < 3:
            N = 3
 
        self.save = [None] * (N+1)
        self.save[1] = 1
        self.save[2] = 2
        self.save[3] = 4
 
    def count_of_combination(self, N):
        if N < 1:
            return 0
        elif self.save[N] != None:
            return self.save[N]
        else:
            result = (self.count_of_combination(N-1)
                      + self.count_of_combination(N-2)
                      + self.count_of_combination(N-3))
            self.save[N] = result
            # print('save[{}]={}'.format(N, result))
            return result
 
def main():
    T = int(input())
 
    counter = Counter()
 
    for i in range(T):
        N = int(input())
        counter.init_save(N)
        cnt = counter.count_of_combination(N)
        print(cnt)
 
if __name__ == '__main__':
    main()