프로그래머스 숫자의 표현 (효율성 테스트 실패)

접근

https://school.programmers.co.kr/learn/courses/30/lessons/12924

dp는 이용해서 값들을 누적해서 풀었다.
하지만 효율성 테스트에서 실패했다.

다른 분의 풀이를 통해서 더 간결한 방법이 있다는 것을 깨달았다.

과정

일단 문제로부터 받는 n의 반절까지만 dp배열에 누적한다.
반절 넘어가면 어차피 연속된 숫자로 n을 만들지 못한다.

        int length=0;
        if(n%2==0) length = n/2 +1 ;
        else length= n/2+2;
        
        
        int[] dp = new int[length];
        
        for(int i=1;i<=length-1;i++){
            dp[i]=dp[i-1]+i;
            System.out.println(dp[i]);
        }

위에서 구한 dp 배열을 가지고 이제 n이 나오는 연속된 수들의 합의 개수를 구해야 한다.

• dp 현재가 n인 경우 answer+1;
• dp 현재가 n이 아닌 경우
  • dp 현재가 n보다 작은 경우 현재보다 +1 나아가기
  • dp 현재-dp[현재보다 작은 인덱스] == n이면 answer+1;
  • dp 현재-dp[현재보다 작은 인덱스] <n이면 break;

        for(int i=1;i<=length-1;i++){
            if(dp[i]<n) continue;
            else {
                if(dp[i]==n) answer++;
                else{
                    for(int j=1;j<i;j++){
                        if(dp[i]-dp[j]==n) answer++;
                        else if(dp[i]-dp[j]<n)break;   
                  
                    }//for
               }//else
                                
           }//else
        }//for
          

효율성 테스트 실패한 나의 풀이

class Solution {
    public int solution(int n) {
        int answer = 1;
        
        if(n==1) return 1;
        
        int length=0;
        if(n%2==0) length = n/2 +1 ;
        else length= n/2+2;
        
        
        int[] dp = new int[length];
        
        for(int i=1;i<=length-1;i++){
            dp[i]=dp[i-1]+i;
            System.out.println(dp[i]);
        }
        
        for(int i=1;i<=length-1;i++){
            if(dp[i]<n) continue;
            else {
                if(dp[i]==n) answer++;
                else{
                    for(int j=1;j<i;j++){
                        if(dp[i]-dp[j]==n) answer++;
                        else if(dp[i]-dp[j]<n)break;   
                  
                    }//for
               }//else
                                
           }//else
        }//for
                               
               
        return answer;
    }
    
}
                             

실패 이유를 생각해보면 일단 n은 1000이하의 자연수이기 때문에
dp배열은 500개의 자리가 필요하고 이를 누적해서 저장한다.

또한 answer을 구하는 과정은 예상해보았을 때 n*(n-1)번의 연산이 발생한다.

더 간결한 다른 분의 풀이

class Solution {
    public int solution(int n) {
        
        
        
        int answer=0;
        
        for(int i=1;i<=n;i++){
            int sum=0;
            for(int j=i;j<=n;j++){
                sum+=j;
                if(sum==n){
                    answer++;
                    break;
                }else if(sum>n) break;
            }
        }
               
        return answer;
    }
    
}