[백준/BOJ] 9461번 : 파도반 수열 (JAVA / 자바)
안녕하세요~ 코딩하는 코알못 코메인입니다.
https://www.acmicpc.net/problem/9461
9461번: 파도반 수열
오른쪽 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 변의
www.acmicpc.net
- 문제 -
난이도 실버 3 문제이다.
자바에서 입력방식은 scanner와 bufferedreader가 있다.
자바를 초반에 접하면 처음에 배우는 입력은 scanner이다. scanner가 bufferedreader보다 편하지만 속도가 느리다.
bufferedreader는 무조건 문자열로 받아오기때문에 정수형이나 실수형 변수에 저장하기 위해서는 입력과 형변환을 해줘야한다.
더 자세한 내용은 아래 글 참고 하면 좋다.
(JAVA / 자바) Scanner 와 Bufferedreader
안녕하세요~ 코딩하는 코알못 코메인입니다. 이번엔 백준 문제 풀면서 계속 언급될 scanner와 bufferedreader에 대한 간단한 정리를 해볼거다. 자바에서 입력은 scanner와 bufferedreader가 있다. 우선 각자
comain.tistory.com
풀이 방법
dp 문제인다. 여느때 처럼 패턴을 찾아 풀면 된다.
친절하게도 1부터 10까지 문제에서 알려줬는데 이것만 봐도 찾기 쉬울 정도로 쉬운 패턴이다.
1 1 1 2 2 3 4 5 7 9
보니깐 자신의 자리보다 2번째 3번째 자리 앞에 값의 합으로 보인다.
그렇게 예제 1번에서 말한 12번까지 가보자.
5부터 12까지 나열해보겠다.
2 3 4 5 7 9 (5+7=12) (7+9=16) 즉 12번째는 16이 된다.
주의 할 점 하나만 보자.
정확히 78번째 값은 1828587033이 나온다. 79번째 값은 int형 범위를 넘어서게 된다.
long으로 잡고 풀자.
코드를 보자.
-풀이-
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int T = Integer.parseInt(br.readLine());
for(int i = 0; i < T; i++) {
int N = Integer.parseInt(br.readLine());
int[] dp = new int[N + 1];
dp[0] = 0;
dp[1] = 1;
//아래 조건은 1이 입력 되었을때 2에 대한 조건을 안받기 위해서.
if(N > 1) {
dp[2] = 1;
for(int j = 3; j <= N; j++) {
dp[j] = dp[j - 3] + dp[j - 2];
}
}
System.out.println(dp[N]);
}
}
}-결과-
아직 코딩 공부가 부족한 필자라 설명과 풀이 방법이 많이 미흡할 수 있다. 코딩 고수분들은 보시고 문제점이 있다면 댓글로 말해주시면 감사한 마음으로 참고 수정 하겠습니다.