[ Baekjoon - 09/17 ] - 2018번: 수들의 합 5

• 문제 링크 : https://www.acmicpc.net/problem/2018

2018번: 수들의 합 5

 

• 소요 시간 : 1시간

 

1. 문제를 읽고 이해하기
   • 제한
     • 시간 : 2초
     • 메모리 : 32MB
   • 문제
     • 정수 N을 연속된 숫자의 합으로 나타낼 수 있는 경우의 수를 출력하는 문제
   • 이해
     • 15라는 숫자가 N에 입력되었다면, 15와 7+8, 4+5+6, 1+2+3+4+5 즉, 4가지 방식으로 나타낼 수 있으므로 답은 4가 된다.
2. 문제를 익숙한 용어로 재정의와 추상화
   • 
   • 입출력 예제에 있던 15와 10을 예로들어 표로 나타내보았다.
3. 문제를 어떻게 해결할 것인가

   • 

   • 빨->주->노 순서로 접근했다
   • 1st 접근)
     표로 나타내어 어떤 규칙이어야 연속적인 숫자의 합으로 결정되는지 생각하다가, 나머지로 구분할 수 있을거라 생각해 하나하나 적어보았다.
     => 2개의 합 : 짝수+홀수 이므로 둘이 더했을때 나머지가 1이된다.
     => 3개의 합 : 짝+홀+짝 이거나 홀+짝+홀 인데, 중간 숫자를 x라 두면 3x라 나타낼 수 있어서 3으로 나눴을때 나머지가 0이된다.  
     => 4개의 합도 위 2,3개의 합과 마찬가지로 본인숫자로 나눴을때 나머지가 0이거나 1인 형태를 이루고자 했지만 숫자들이 규칙적으로 나타나지 않아서 이 방법은 아니라고 생각했다.
   • 2nd 접근)
     몇개의 합이냐에 따라 홀수와 짝수의 조합으로 나타낼 수 있고, 등차수열로 보면 식으로 나타낼 수 있어서 공식화를 통해 점화식으로 나타내려 했지만 등차 뿐만아니라 첫항이나 마지막항이 필요한 공식이므로 표현하기가 난해해 다른 방법을 생각해보기로 했다.
   • 3rd 접근)
     누적합을 이용해 투포인터로 찾아보고자 생각을 했고, 이 방법이 제일 적합하다고 생각했다.
4. 위 계획을 검증
   • 누적합 배열을 만들면
     1번 인덱스는 1까지의 합이므로 1
     2번 인덱스는 2까지의 합이므로 1+2 = 3
     3번 인덱스는 3까지의 합이므로 1+2+3 = 6
     4번 인덱스는 4까지의 합이므로 1+2+3+4  = 10
     이렇게 나타낼 수 있다.
   • 즉, 2+3의 합을 구하려면 배열[3] - 배열[1]로 구할 수 있다. 즉 값을 가르키는 포인터(인덱스)가 2개만 있으면 구할 수 있다.
5. 계획 수행 (실제코드 작성)

   • import java.util.*;
     import java.io.*;
     
     public class Main {
         static int N,sum=0,finalN,startN,result=0;
         static int[] accSum;
     
         public static void main(String[] args) throws IOException {
             //System.setIn(new FileInputStream("src/input.txt"));
     
             BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
             N = Integer.parseInt(br.readLine());
     
     		//누적합 배열 생성
             accSum = new int[N+1];
             for (int n = 1; n < N; n++) {
                 sum+=n;
                 accSum[n]=sum;
             }
             
             //startN이 앞을 가르키는 포인터, finalN이 뒤를 가르키는 포인터
             finalN = N-1;
             startN = finalN-1;
             
             while(true){
                 if(startN<0){
                     result+=1;
                     break;
                 }else if(finalN<0){
                     break;
                 }
     
                 if(accSum[finalN]-accSum[startN]==N){
                     result+=1;
                     finalN-=1;
                 }else if(accSum[finalN]-accSum[startN]>N){
                     finalN-=1;
                 }else{
                     startN-=1;
                 }
             }
             System.out.println(result);
         }
     }

• 결과
  N이 1일때를 고려하지 않아서 startN이 -1인덱스가 되어 첫 시도에 틀렸고 이를 고치니 맞았다.