1) sumArr
: 숫자 0부터 인덱스까지의 합을 저장한다.
예시
Index 0 1 2 3 4 5 6 7 ... value 0 1 3 6 10 15 21 28 ...
연속되는 숫자들을 합해서 숫자 n을 만드는 경우의 수는 다음과 같은 형태를 띄게된다.
ex) n = 15일 경우
1 + 2 + 3 + 4 + 5 : sum[5] - sum[0]
4 + 5 + 6 : sum[6] - sum[3]
7 + 8 : sum[8] - sum[6]
15 : sum[15] - sum[14]
public int solution(int n) {
int answer = 0;
int tempSum = 0;
int diff = 0;
ArrayList<Integer> sumArr = new ArrayList<Integer>();
//인덱스 0에 대한 값(0)을 넣어주고 시작한다.
sumArr.add(0);
//tempSum 값 초기화
//i가 3일 경우 숫자 1~3의 sum을 저장함
for(int i=1; i<=n; i++) {
tempSum = sumArr.get(i-1) + i;
sumArr.add(tempSum);
}
//startIdx : 탐색을 시작할 인덱스, endIdx : 마지막 숫자 (ex. 1+2+3 으로 숫자 n을 만들 수 있는지 확인하려 할 때, endIdx는 3이다)
int startIdx, endIdx;
startIdx = endIdx = 0;
//endIdx가 가르키는 값이 n보다 크거나 같을때까지로 이동한다
while(true) {
if(sumArr.get(endIdx) >= n) { break; }
endIdx++;
}
//숫자 n을 만들 수 있는 경우의 수 카운팅
while(endIdx < sumArr.size()) {
diff = sumArr.get(endIdx) - n; //n을 구하기 위해서 빼야할 값
while(startIdx < endIdx) {
if(diff == sumArr.get(startIdx)) { //n값을 구할 수 있는 경우
answer++; break;
} else if(diff < sumArr.get(startIdx)) { //endIdx이 마지막 숫자일 경우 n값을 구할수 없음.
break;
} else {
startIdx++;
}
}
endIdx++;
}
return answer;
}