코테/백준
[백준/JAVA] 9461번: 파도반 수열
imname1am
2023. 5. 30. 21:25
반응형
🔺 문제
9461번: 파도반 수열
오른쪽 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 변의
www.acmicpc.net
🔺 코드
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
|
import java.util.*;
import java.io.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
// DP 배열 채우기
long[] P = new long[101];
P[1] = P[2] = P[3] = 1;
for(int i = 4 ; i <= 100 ; i++) {
P[i] = P[i - 3] + P[i - 2];
}
// 입력
int T = Integer.parseInt(br.readLine());
while(T --> 0) {
int num = Integer.parseInt(br.readLine());
sb.append(P[num]).append("\n");
}
System.out.println(sb.toString());
br.close();
}
}
|
cs |
✅ 해결 아이디어
✔ DP
- P[N] : 나선에 있는 정삼각형의 변의 길이
- 점화식 :P[ i ] = P[ i - 3 ] + P[ i - 2 ]
또 다른 점화식은 P[i] = P[i - 1] + P[i - 5] 라고 함.
💥 유의사항
• 100번째 항 요청 시, int형 범위를 넘기므로 배열을 long형으로 만들어야 값이 제대로 나온다. (참고1, 참고2)
🔺 다른 풀이들
- 복습용... 좋은 설명
[백준] 9461번 : 파도반 수열 - JAVA [자바]
st-lab.tistory.com
- 그림 과정
[백준] 9461번: 파도반 수열 - JAVA
🔗 문제 링크 BOJ 9461번: 파도반 수열 9461번: 파도반 수열 오른쪽 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다음과 같은 과정
girawhale.tistory.com
💬 느낀 점
앞으로 이 문제 나오면 DP & 점화식 기억해둬야지...
| 1회독 | 2회독 | 3회독 | 4회독 | 5회독 |
| V |
반응형