문제

[프로그래머스] 숫자의 표현
https://school.programmers.co.kr/learn/courses/30/lessons/12924

풀이

조건

• 자연수 n을 연속한 자연수들로 표현 하는 방법이 여러개이다.

  15인 경우

  • 1 + 2 + 3 + 4 + 5 = 15
  • 4 + 5 + 6 = 15
  • 7 + 8 = 15
  • 15 = 15

풀이 순서

• 누적합을 사용하면 연속된 구간의 합을 구할 수 있다.

코드

Java

import java.util.*;

class Solution {
    public int solution(int n) {
        int answer = 0;
        
        // 1 ~ n 누적합 구하기
        int[] dp = new int[n + 1];
        for(int i = 1; i <= n; i++) {
            dp[i] = dp[i - 1] + i;
        }
        
        // 목표값 찾기 -> 이분탐색 활용
        for(int i = 1; i <= n; i++) {
            int target = dp[i] - n;
            if(binarySearch(dp, 0, n, target)) {
                answer++;
            }
        }
        
        return answer;
    }
    
    // 이분탐색으로 목표 값 찾기
    boolean binarySearch(int[] arr, int start, int end, int target) {
        while(start <= end) {
            int mid = (start + end) / 2;
            if(arr[mid] < target) {
                start = mid + 1;
            } else if(arr[mid] > target) {
                end = mid - 1;
            } else {
                return true;
            }
        }
        return false;
    }
}

정리

• 다른 사람들은 2중 for문을 돌리면서 합이 n보다 커지면 종료시키는 방법으로 해결했다.