[백준] 1789번 : 수들의 합 - Java(자바)

첫 스터디를 zoom으로 진행하였습니다. 처음 하는 발표라서 떨려서 횡설수설 하였는데 다음엔 더 잘 하도록 노력할려고 합니다. 미리 발표를 혼자 해봤지만 다음엔 2번 해봐야지 싶습니다.

이번 문제는 서로 다른 N개의 자연수의 합 S를 알 때 자연수 N의 최대 개수를 구하는 문제였습니다.
그리드 알고리즘으로 접근하여서 풀었는데 그리드 알고리즘이란 쉽게 매 순간 최선의 선택을 하는 알고리즘입니다. 예를 들어 저의 눈 앞에 치킨과 고등어 튀김과 방어 순살 조림 이렇게 세 가지 메뉴와 손에는 3만원이라는 돈이 존재하고 한 가지의 메뉴만을 고를 수 있다면 여기서의 최선의 선택은 치킨이 됩니다.
다음은 사이드 메뉴를 감자 튀김, 김치, 알타리 무침에서 고르게 되고 이 중 치킨과 가장 잘 맞는 감자 튀김을 고르게 됩니다.이렇게 계속 매 순간 가장 이상적인 값을 고르는게 그리드 알고리즘입니다. 하지만 이렇게 하나 하나 모인 선택들의 집합이 최선의 결과가 된다고는 확답할 수 없습니다. 예를 들어 첫 선택에서 치킨을(2만원) 고르고 두 번째에서 감자 튀김을(9천원) 골랐다고 치고 세 번째 선택에서는 갑자기 랍스타 90% 세일을 해서 랍스타(원가는 10만원, 세일 후 1만원), 깍두기(천원), 김자반(2천원) 이렇게 세 가지 경우가 존재하게 된다면 그리드 알고리즘적 접근에서는 매 순간 최선을 선택하였기에 마지막 선택에서 최선의 결과인 랍스타 + 기타 메뉴를 고를 수 없고 깍두기를 고를 수 밖에 없습니다. 하지만 매 순간 최선의 선택을 하였기에 모든 선택들이 모인 집합은 최선의 선택의 근사치에 매우 가까워 질 가능성이 높다는 이론입니다.

Step 0. 해답 코드

import java.util.Scanner;

//Greedy Algorithm
//매 순간 최적의 경우를 구한다.
//그렇기에 매 순간 구한 최적의 수 들의 집합이 최선의 선택이 아닐 수도 있다.
//또한 매 순간의 선택은 다른 순간의 선택에 영향을 주면 안 된다.
//서로 다른 N개의 자연수의 합이 S라고 한다. S를 알 때, 자연수 N의 최댓값은 얼마일까?

public class Su_hap_1789 {
	public static int Search_N(long S) { //객체 생성 없이 메소드 사용 가능!
		int N = 0; //서로 다른 N개의 자연수 개수. cnt. 
		long sum = 0L; //N의 합. N의 범위가 int 형 범위를 벗어나므로 long으로 선언.
		int i = 0; //최대 N의 개수를 구해야 하므로 제일 작은 1부터 시작.
		while(true) {
			sum += ++i;
			
			if (sum > S) {
				return N;
			}
			N++;
		}
	}
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		long inp = sc.nextLong(); 
		//서로 다른 자연수 N개가 필요.
		//즉 최적의 판단은 가장 작은 수 부터 더해나가면 된다.
		System.out.println(Search_N(inp));
		sc.close();
	}
}

정적 메소드를 사용하여 문제를 풀었습니다.

Step 1. 문제 접근

문제의 예에서 200을 예로 들었기에 200을 기준으로 설명드리자면 자연수 N의 개수가 최대로 많을려면 N의 원소들은 가장 작은 수 부터 시작하여야 합니다. 만약 가장 큰 200으로 시작을 한다면 N은 200 단 하나 뿐이게 되지만 1부터 시작 한다면 서로 다른 자연수는 1 + 2 + 3 + ....해서 총 19개가 될 수 있는 것입니다.

Step 2. 문제 해결

문제에서 주어지는 자연수의 범위는 int형의 범위를 넘기에 long 타입으로 선언하였습니다.

public static int Search_N(long S) { //객체 생성 없이 메소드 사용 가능!
		int N = 0; //서로 다른 N개의 자연수 개수. cnt. 
		long sum = 0L; //N의 합. N의 범위가 int 형 범위를 벗어나므로 long으로 선언.
		int i = 0; //최대 N의 개수를 구해야 하므로 제일 작은 1부터 시작.
		while(true) {
			sum += ++i;
			
			if (sum > S) {
				return N;
			}
			N++;
		}
	}

변수는 총 4개를 만들었으며 매개변수 S는 문제에서 주어지는 S값으로 N은 저희가 구하는 자연수 N개를 의미하고 있습니다. sum은 저희가 작은 값부터 더해 나갈 때 사용할 변수입니다. 예를 들어 200의 경우는 가장 작은 1부터 시작해서 2 3 4..이렇게 1씩 늘려주면서 더해줄 것입니다. 즉 sum은 1 + 2 + 3 +....의 값들이 들어가게 될 것입니다. i는 가장 작은 1부터 시작해서 1씩 증가하도록 만들었습니다. 메소드 안에서는 sum 값을 1씩 늘려주면서 더해줬고 if문을 통해 i값을 계속 더해주는 sum이 처음 입력 받은 S보다 작다면 아직까지는 sum의 범위가 처음 입력 받은 S의 범위를 넘지 않았기에 N의 값을 1 늘려줬습니다. 그러다가 sum 값이 매개변수 S보다 커지면 범위를 넘어간 것이기 때문에 return을 통해 메소드를 종료 시키고 N값을 출력하도록 하였습니다.

Step 3. 느낀 점

문제 자체는 매우 쉬운 문제였습니다. 문제를 푼 후 혹시 너무 쉽지 않았나 싶어서 다른 분들에게 다음엔 더 어려운 문제를 풀자는 식으로 말씀 드렸는데 지금 난이도로 이어가자는 의견이 나와서 앞으로도 zoom 난이도는 이정도 수준일 거 같습니다. 그렇기에 zoom 알고리즘 문제는 제가 계속 공부를 할 명분(?) 혹은 리프래쉬를 하기 위해 활용하고자 하고 좀 더 어려운 알고리즘 문제는 개인적으로 풀 생각입니다. 다음 zoom 스터디는 다음 주 화요일 입니다!

출처 : 백준 1789번 https://www.acmicpc.net/problem/1789