🐣 백준 Q2018 - 수들의 합5 (java)

문제

---

• 백준 Q2018 - 수들의 합5

풀이

---

그림으로 봤을 땐 이해가 갔는데
코드로 보니 왜 이런지 하나하나 결과를 보는 게 좋겠다고 생각했다.

이 문제는 백준의 2018번 문제 ‘수들의 합5’이다.

투 포인터 알고리즘을 이용해 풀어볼 것이다.
start 포인터와, end 포인트를 1에 두고 시작한다.
연속된 숫자의 합을 구하는 문제이니
start ~ end 까지의 합을 구하는 방법을 이용한다.

일단 수도 코드로는 이렇게 된다고 한다. - 두잇책 참고

N 변수 저장
사용 변수 초기화(count = 1, start_index = 1, end_index = 1, sum = 1)
while(end_index != N) {
	if(sum == N) count 증가, end_index 증가, sum값 변경
	else if(sum > N) sum값 변경, start_index 증가
	else if(sum < N) end_index 증가, sum값 변경
}
count 출력하기

구현한 코드는

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Q2018_수들의합5 { 
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int N = Integer.parseInt(br.readLine());
		
		int start = 1, end = 1, sum = 1, count = 1;
		
		while (start != N) {
			if (sum == N) {
				count++;
				end++;
				sum += end;
			} else if (sum > N) {
				sum -= start;
 				start++;
			} else if (sum < N){
				end++;
				sum += end;
			}
		}
		System.out.println(count);
	}
}

/*
----- 예제 입력 1 -----
15
----- 예제 출력 1 -----
4
*/

예제인 15는 너무 크니
N = 5 라 가정해보겠다.
나올 수 있는 값은 (2,3), (5)로
count = 2이 정답이다.

1. 처음으로는 N 값 자체인 (5)인 경우를 count에 미리 넣어주고 시작한다.
2. start 포인터가 1~ 반복하게 되고
3. 더이상 start 포인터 1로 할 수 있는 게 없다면,
   1을 더해 2로 start 포인터를 옮겨서 진행한다.
4. end 포인터를 너무 크게 잡아
   수들의 합인 sum이 구하려는 수보다 커진다면,
   해당 end 포인터를 앞으로 한칸 옮겨 진행한다.
5. 원하는 값을 찾아 count를 올려주었다면
   다음 경우를 찾아야 하므로
   end 포인터를 뒤로 한칸 옮겨 다음 경우를 찾기 시작한다.

(5)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Q2018_수들의합5 { 
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int N = Integer.parseInt(br.readLine());
		
		int start = 1, end = 1, sum = 1, count = 1; // 👉 본인인 숫자 N을 미리 카운트해 두고

		while (start != N) { // 여기에서는 본인 숫자N을 세는 일을 하지 않는다.
			if (sum == N) {
				count++;
				end++;
				sum += end;
			} else if (sum > N) {
				sum -= start;
 				start++;
			} else if (sum < N){
				end++;
				sum += end;
			}
		}
		System.out.println(count);
	}
}

이제 초기 숫자인 1을 넣어 while문을 실행해본다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Q2018_수들의합5 { 
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int N = Integer.parseInt(br.readLine());
		
		int start = 1, end = 1, sum = 1, count = 1;
		
		// N = 5, start = 1
		while (start != N) {
			
			// case A (sum = N)
			if (sum == N) {
				count++;
				end++;
				sum += end;
				// 4️⃣ sum(5) = N(5)
				// 👉 count(2)
				// end(4)
				// sum(9) = sum(5) + end(4)
				//---> start(2), end(4), sum(9), count(2) 

			// case B (sum > N)
			} else if (sum > N) { 
				sum -= start;
				start++;
				// 3️⃣ sum(6) > N(5)  
				// sum(5) = sum(6) - start(1)
				// start(2)  
				//---> start(2), end(3), sum(5), count(1)
				// 👉 (2, 3)
        
			// case C (sum < N)
			} else if (sum < N){
				end++;
				sum += end;
				// 1️⃣ sum(1) < N(5)    
				// end(2) 
				// sum(3) = sum(1) + end(2)  
				//---> start(1), end(2), sum(3), count(1)
				// 2️⃣ sum(3) < N(5)
				// end(3)
				// sum(6) = sum(3) + end(3)
				//---> start(1), end(3), sum(6), count(1)
			}
		}
		System.out.println(count);
	}
}

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Q2018_수들의합5 { 
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int N = Integer.parseInt(br.readLine());
		
		int start = 1, end = 1, sum = 1, count = 1;
		
		// N = 5, start(2), end(4), sum(9), count(2) 
    while (start != N) { // 5️⃣ start(5) = N(5) ---> 종료
		
			// case A (sum = N)
			if (sum == N) {  
				count++;
				end++;
				sum += end;
				
			// case B (sum > N)
			} else if (sum > N) {
				sum -= start;
 				start++;
				// 1️⃣ sum(9) > N(5)
				// sum(7) = sum(9) - start(2)
				// start(3)
				//---> start(3), end(4), sum(7), count(2)
				// 2️⃣ sum(7) > N(5)
				// sum(4) = sum(7) - start(3)
				// start(4)
				//---> start(4), end(4), sum(4), count(2)
				// 4️⃣ sum(9) > N(5)
				// sum(5) = sum(9) - start(4)
				// start(5)
				//---> start(5), end(5), sum(5), count(2)
        
			// case C (sum < N)
			} else if (sum < N){
				end++;
				sum += end;
				// 3️⃣ sum(4) < N(5)
				// end(5)
				// sum(9) = sum(4) + end(5)
				//---> start(4), end(5), sum(9), count(2) 
			}
		}
		System.out.println(count);
	}
}

답은 2!

결과

---

1. 자신인 N은 미리 count 해두고
2. 그외의 경우를 구해 count해주고
3. 마지막은 start(5) = end(5) = sum(5) 가 되면서 while문 종료