[BaekJoon] 백준 1789번 _ 수들의 합 for JAVA _ 그리디 알고리즘

 

https://www.acmicpc.net/problem/1789

1789번: 수들의 합

 

 

 

문제

 

 

 

---

 

 

당연히 작은 수부터 더해가면서 살펴보면 된다.

 

 

200은 왜 출력이 19냐면

 

 

1 + 2 + 3 + … + 18 + 29 해서 19개가 된다.

 

 

여기서 ... 18 + 19 = 190 이라서 10은 중복 사용을 못하므로 그냥 29를 더해버려야 한다.

 

 

다른 숫자도 마찬가지고 나누어 떨어지지 않으면 그냥 + 나머지수 일케 해야함

 

 

 

 

코드

package Baek;

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


public class Baek1789 {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		long S = Long.parseLong(br.readLine());
		
		long count = 0;
		for(long i = 1; i <= S; i++) {
			if(S - i == 0) {
				count++;
				break;
			}
			else if(S - i < 0) {				
				break;
			}
			else {
				S -= i;
				count++;
			}
		}
		
		System.out.println(count);
	}

}

 

 

 

주의할건 int 타입보다 S의 수가 크므로 long 타입을 사용해줘야한다.

 

 

나누어 떨어지면 count++; 하고 끝내주고 안나눠지면 19를 더한 상태에서 그냥 끝내준다. (18 다음 29를 더하나 19를 더하고 끝내나 +1인건 같아서)

 

 

 

 

성능

 

 

 

 

---

 

다른 사람 코드

 

 

 

 

 

 

그냥 더해가는게 S보다 크면 멈추고 count - 1을 출력해줬다.

 

 

왜냐면 19 다음 20을 더해서 count++ 해준 뒤 sum이 S보다 큰걸 알아챘으니까 -1 함으로써 출력해줌