파도반수열 문제 분석

문제보고오기
그림을 보면 해당 형태로 그려진다.

이와 같은 문제는 규칙성을 찾는게 가장 중요하므로, 그림을 계속 이어서 그려본다.

다음 그림이 어떻게 그려지는게 순서대로 표기해본다.

규칙성을 찾으면, 점화식 형태로 나타낸다.

문제 풀이 방식 설정

문제의 형태가
1. 하위 문제에 대한 중복
2. 부분 문제에 대한 최적
의 형태를 띄고 있으므로, 동적 프로그래밍 방식으로 해결할 수 있다.

문제 풀이

1. 문제 요구사항

• 입력과 출력을 만족할 수 있도록 입력과 출력을 연산할 수 있어야 한다.

2. 해결 코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;

public class Main {
  public static void main(String[] args) {
    // 콘솔 입력 설정 및 변수 입력
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    // 변수 설정
    int T;
    int N;

    // 100을 넣는 경우 int 자료형을 초과함
    ArrayList<Long> P = new ArrayList<>();
    // 초기 값 5개를 insert
    P.add(1L);
    P.add(1L);
    P.add(1L);
    P.add(2L);
    P.add(2L);

    try {
      // input T
      T = Integer.parseInt(br.readLine());

      for (int i = 0; i < T; i++) {
        // input N
        N = Integer.parseInt(br.readLine());
        // 초기값 이거나, 이미 진행한 연산이면
        if (N <= P.size()) {
        }
        // 만약 아직 진행하지 않은 연산이면 ArrayList 에 넣어주기
        else {
          for (int j = P.size(); j <= N-1; j++) {
            P.add(P.get(j-1) + P.get(j-5));
          }
        }
        System.out.println(P.get(N-1));

      }

    } catch (Exception e) {
      e.printStackTrace();
    }


  }
}

3. 분석 후, 코드 수정

해결 코드를 분석해보면, Main class의 main 메서드에 전부 넣은 상황이라, 어디가 입력이고, 어디가 해결코드인지 분간하기가 힘들다.

해당 main 메서드에 꼭 필요한 함수만 들어가게 수정해줄 수 있다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;

public class Main {
  public static void main(String[] args) {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    
    // 변수 설정
    int T;
    int N;

    // 100을 넣는 경우 int 자료형을 초과함
    ArrayList<Long> P = new ArrayList<>();
    // 초기 값 5개를 insert
    P.add(1L);
    P.add(1L);
    P.add(1L);
    P.add(2L);
    P.add(2L);


    try {
      // input T
      T = Integer.parseInt(br.readLine());

      for (int i = 0; i < T; i++) {
        // input N
        N = Integer.parseInt(br.readLine());

        // output f(N)
        System.out.println(findTriangleSizeLength(N, P));

      }

    } catch (Exception e) {
      e.printStackTrace();
    }


  }
    
  static Long findTriangleSizeLength(int N, ArrayList<Long> P) {
    // 만약 아직 진행하지 않은 연산이면 ArrayList 에 넣어주기
    if (N > P.size()) {
      for (int j = P.size(); j <= N-1; j++) {
        P.add(P.get(j-1) + P.get(j-5));
      }
    }
    // 초기값 이거나, 이미 진행한 연산이면 패스하고 리턴
    return P.get(N-1);
  }

}

4. 발생할 수 있는 오류

틀렸습니다.

1. f(100)까지 가면 int 자료형의 표현범위를 초과하므로 저장 배열이 Long 형태가 아닌경우 틀림

시간초과

1. 재귀함수를 사용하면 중복되는 연산이 많아져서 시간초과가 발생할 수 있음