Today Sulim Learned

silver 5. 수들의 합(1789)

30 Jan 2022 | 알고리즘 프로그래밍 자바

silver 5. 수들의 합 (1789)

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

문제

서로 다른 N개의 자연수의 합이 S라고 함. S를 알 때, 자연수 N의 최댓값은 얼마일까?

입력: 자연수 S (1 <= S <= 4,297,967,295)

출력: S의 최댓값 출력

풀이

  • 아이디어: 1부터 순서대로 값을 더해나가다가 더한 값이 주어진 수 S보다 커지면 프로그램 종료

    • count 변수에 몇 개의 수를 더했는지 저장
    • S보다 자연수를 더한 값이 커지면 count의 값을 1 빼준 후 출력

    예를 들어 S가 50이라고 가정

    • 1+2+3+4+5+6+7+8+9+10 = 55 (이때의 count 값은 10)
    • 55에서 5만 빼주면 S가 되므로 count에서 1만 감소시키면 됨
import java.util.*;

public class Main{
  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
    
    int count = 0;	// 더한 값의 개수를 저장
    long add = 1;	// sum에 더해나갈 값
    long sum = 0;	// 자연수들의 합을 저장
    
    // long 변수 사용 이유: 입력 값의 범위가 int형이 담을 수 있는 범위를 넘어감
    long num = sc.nextLong();	

    while (true){
      sum += add ++;	// sum에 add 값을 더한 후, add 값 1 증가
      count ++;		// count 값 1 증가 

      // sum의 값이 num의 값보다 커지면 count를 1 감소시키고 while 문을 벗어남
      if (sum > num) {	
        count --;
        break;
      }
    }
      
    // count 값 출력
    System.out.println(count);
  }
}

Related Posts