[Python] 4172번 sqrt log sin

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

4172번: sqrt log sin

---

 

22/10/08

 

 

DP라고 보기에도 조금 민망할 정도로, 이미 점화식을 문제에서 다 주었다.

 

이를 메모이제이션 기법을 활용하여 단순 구현만 하면 되는 문제이다.

---

 

문제 접근 방식:

 

 

처음에는 입력마다 DP값을 구해주도록 했는데, 시간초과가 났다.

 

그래서 입력 전에 미리 DP값을 다 구해주고(전처리 과정), 입력 할 때마다 그 값을 출력하도록 바꿔주었다.

 

구현은 math모듈의 floor함수와 sin함수, log함수를 가져다 썼다.

---

아래는 내가 위의 접근 방식과 같이 작성한 파이썬 코드이다. 더보기를 누르면 확인할 수 있다.

# 4172번 sqrt log sin
# DP
from math import *
seq = [1 for _ in range(1000000+1)]
for i in range(1,1000000+1):
    seq[i] = (seq[floor(i-sqrt(i))] + seq[floor(log(i))] + seq[floor(i*sin(i)*sin(i))]) % 1000000
while True:
    n = int(input())
    if n == -1:
        break
    print(seq[n])