[B0J]수들의 합(1789번)

티어 : Sliver 5
정답여부 : 오답
알고리즘 유형 : 수학, 그리디 알고리즘
시간 제한 : 2초

 

 

💡문제

● 수들의 합

 

 

💡입력

200

 

 

💡출력

19

 

 

💡문제 분석

서로 다른 N 개의 자연수의 합이 S가 될 때 가장 큰 N 자연수를 구하면 되는 문제
-> 자연수 합 S 보다 작을 수도 있고 딱 맞을 수도 있음

 

 

💡알고리즘 설계 

1. 자연수 합을 입력 받음
2. 자연수는 1부터 시작하는데 자연수의 합을 더하는 sum의 값이 S보다 큰 경우 for 문을 나감
3. max_number에 i값을 넣어서 출력

 

 

💡시간복잡도

• O(N)

 

 

💡틀린 코드

import java.io.*;

public class Main {

	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int S = Integer.parseInt(br.readLine());
		int sum = 0; // 자연수 들의 합 
		int max_number = 0; // 가장 큰 자연수 -> 우리가 찾아야 할 값 
		for(int i = 1; i < S; i++) { // 자연수는 1부터 시작 
			sum+= i;
			if(sum > S) { // S를 넘으면 종료 
				break;
			}
			max_number = i;
		}
		System.out.println(max_number);

 

 

💡 틀린 이유

문제에서 주어진 S가 첫째 줄에 자연수 S(1 ≤ S ≤ 4,294,967,295)가 주어진다. -> int의 최대값인 2,147,483,647을 넘기 때문이다. 즉 Int값을 초과하여 long 타입을 써줘야 함

 

 

💡정답 코드

import java.io.*;

public class Main {

	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		long S = Long.parseLong(br.readLine());
		long sum = 0; // 자연수 들의 합 
		int max_number = 0; // 가장 큰 자연수 -> 우리가 찾아야 할 값 
		for(int i = 1; i< Integer.MAX_VALUE ; i++) { // 자연수는 1부터 시작 
			sum+= i;
			if(sum > S) { // S를 넘으면 종료 
				break;
			}
			max_number = i;
		}
		System.out.println(max_number);

	}

}

 

 

💡 느낀점 or 기억할정보

주어진 범위값 잘 보자!