1, 2, 3 더하기 4 (15989번) - 백준 (BOJ)

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

15989번: 1, 2, 3 더하기 4

 

백준 - 1, 2, 3 더하기 4 (15989번)

 

난이도 : Silver 1

알고리즘 : Mathematics, Simulation, (Dynamic Programming)

풀이 소요 시간 : 60분

 

import sys
input = sys.stdin.readline


def count_cases(n):
    if n <= 3:
        return n
    answer = 0
    if n % 6 < 3:
        answer += (n>>1) + 1
        answer += count_cases(n-3)
    else:
        answer += (n//3) + 1
        answer += ((n>>1)+((n%3)>>1)) * (((n//3)+1)>>1)
    return answer


if __name__ == '__main__':
    for _ in range(int(input())):
        print(count_cases(int(input())))

 

n의 범위가 10,000보다 작거나 같은 자연수이기 때문에

백준 "동전 1" 문제(2293번)와 동일하게, Dynamic Programming으로 쉽게 풀 수 있는 문제였다.

2293번의 순한 맛 정도 되는 문제.

이렇게 DP로 풀면 시간복잡도가 O(N)이 된다.

 

하지만 수학적으로 접근해서 점화식을 이용해 풀면,

O(1)으로 해결할 수 있다

 

구현 연습도 할 겸 O(1)으로 풀어보다가 1시간이나 걸렸다.

시간 단축을 위해 좀 더 집중하는 연습을 해야겠다.