✔️문제
오른쪽 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 변의 길이를 k라 했을 때, 그 변에 길이가 k인 정삼각형을 추가한다.
파도반 수열 P(N)은 나선에 있는 정삼각형의 변의 길이이다. P(1)부터 P(10)까지 첫 10개 숫자는 1, 1, 1, 2, 2, 3, 4, 5, 7, 9이다.
N이 주어졌을 때, P(N)을 구하는 프로그램을 작성하시오.
⌨️입력
첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, N이 주어진다. (1 ≤ N ≤ 100)
🖥️ 출력
각 테스트 케이스마다 P(N)을 출력한다.
분류
다이나믹프로그래밍(DP), 일반수학(math)
✔️풀이
자세한 풀이는 사진을 통해서 설명하겠다.
🧑💻풀이 코드
import sys
input = sys.stdin.readline
p = [0] * 101
p[0], p[1], p[2] = 1,1,1
for k in range(3,101,1):
p[k] = p[k-2] + p[k-3]
for _ in range(int(input())):
print(p[int(input())-1])결과
시간 메모리 32ms 32412 KB
👁️🗨️ 코멘트
i) 일단 문제 이름부터 보자
- 문제이름부터가 『파도반 수열』이다.
고등학교를 나왔다면 적어도 '수열'이라는 것이 수학이라는 것을 알 것이다.
바로 뒤도 안 돌아보고 brrrrrrr 떨면서 아하! 먜쓰몌뤾!(mathmetics)
ii) 그림을 보자
-
백준같은 문제가 그림을 왜 줄까?
진지하게 고민해봐야 하는 것이다
-
적어도 문제에 도움이 될려면 된거지, 문제 푸는데 하등 도움이 안될거라면 왜 줬을까?
능지가 있다면 바로 그림을 보고아하 그림이 뭔가 규칙적이네? 수학이네? DP로구나! 점화식 땅땅땅!!
이 판단이 빨리 서야한다.
iii) 쓰자!
-
풀이 사진을 보면 p(1)부터 p(10)까지 직접 쓴 게 보일 것이다.
왜 썼을까?
규칙 볼라고 ㅋ
쓰자! 제발 쓰자! 우리들의 머리는 생각보다 멍청하다. 쓰자.
iv) 라이브러리
- 파이썬은 너무 느리다.
다들 아는 이야기이지만 너무 느리다.
다음과 같은 라이브러리를 불러오면 제법 빨라진다. 알아두자.
import sys
input = sys.stdin.readline
늙고병듦.