스파르타 알고리즘 트랙 문제 1일차 - 1 #2839 설탕 배달

문제

상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕공장에서 만드는 설탕은 봉지에 담겨져 있다. 봉지는 3킬로그램 봉지와 5킬로그램 봉지가 있다.

상근이는 귀찮기 때문에, 최대한 적은 봉지를 들고 가려고 한다. 예를 들어, 18킬로그램 설탕을 배달해야 할 때, 3킬로그램 봉지 6개를 가져가도 되지만, 5킬로그램 3개와 3킬로그램 1개를 배달하면, 더 적은 개수의 봉지를 배달할 수 있다.

상근이가 설탕을 정확하게 N킬로그램 배달해야 할 때, 봉지 몇 개를 가져가면 되는지 그 수를 구하는 프로그램을 작성하시오.

 

해결 과정

주어진 수를 5의 배수와 3의 배수의 합으로 표현하는 코드를 작성하는 문제이다.

 

문제를 보자마자 즉시 떠울린 방법은, N이 0부터 14일 때의 답을 구한 후, 조건문을 이용해 N을 15로 나누었을 때의 나머지를 이전에 구한 답과 매칭시키는 것이었다.

 

하지만 이 방법은 과정도 번거롭고, 봉지의 용량이 커질 수록 사전에 구해야 하는 답과 조건문의 조건 또한 많아지기에 코드의 이점을 전혀 살리지 못한 방법이라 생각했다. (0부터 14일 때의 답을 코드로 구현한다고 해도 그리 좋은 방법은 아니다.)

 

따라서 조금 생각을 달리 해서 더 적은 개수의 봉지에 생각이 머물렀다.

3킬로그램 봉지 5개를 옮기는 것 보다 5킬로그램 봉지를 3개 옮기는 것이 더 빠른데, 그렇다는 말은 3킬로그램 봉지의 경우의 수는 0, 1, 2, 3, 4 총 5가지 뿐이다.

따라서 위 5가지 중, 나머지를 5킬로그램 봉지로 해결할 수 없다면 -1을 출력, 그 외에는 봉지 수의 합을 출력하는 코드를 작성하였다.

import java.util.Scanner; public class Main {     public static void main(String[] args) {         Scanner a = new Scanner(System.in);         int n = a.nextInt();         int caseint = -1;          for (int i =0;i<5;i++){             if(((n-(i*3))%5 == 0)){                 caseint = i;                 break;             }         }         if(caseint==-1){             System.out.println(-1);         }         else{             System.out.println(caseint + (n-(caseint*3))/5);         }     } }

3킬로그램 봉지의 경우의 수를 for문을 이용해 확인하고, 그 중 나머지를 5로 나누어 나머지가 0일 때의 3킬로그램 봉지 수를 초기값이 -1인 caseint 변수에 저장하였다. 그 후 caseint가 변경되어 -1이 아닐 경우에는 총 봉지 수 합을, 조건문을 통과하지 못해 변수값이 그대로 -1인 경우에는 -1을 출력하는 코드를 작성하였다.

 

그러나 위의 코드를 제출했을 때 틀렸다는 답변을 받았다. 왜 틀린 것인지 살펴보았는데, 입력받은 N의 값이 12보다 작아 조건문의 n-(i*3) 값이 음수가 되었어도 5로 나누어 떨어지는 경우가 있었고, 이 때문에 정답이 -1인 조건임에도 caseint의 값이 변경되어 오답을 출력하였다.

 

따라서 for문 첫 단에 n-(i*3) 값이 음수일 경우, 반복문을 실행하지 않도록 설정하여 문제를 해결하였다.

import java.util.Scanner; public class Main {     public static void main(String[] args) {             Scanner a = new Scanner(System.in);             int n = a.nextInt();             int caseint = -1;             for (int i =0;i<5;i++){                 if(n-(i*3)<0)                     break;                 if((n-(i*3))%5 == 0){                     caseint = i;                     break;                 }             }             if(caseint==-1){                 System.out.println(-1);             }             else{                 System.out.println(caseint + (n-(caseint*3))/5);             }         }     }

그렇게 수정한 코드는 기대했던 대로 맞았다는 답변을 받을 수 있었다.

 

 

#4948 베르트랑 공준

문제

베르트랑 공준은 임의의 자연수 n에 대하여, n보다 크고, 2n보다 작거나 같은 소수는 적어도 하나 존재한다는 내용을 담고 있다.

이 명제는 조제프 베르트랑이 1845년에 추측했고, 파프누티 체비쇼프가 1850년에 증명했다.

예를 들어, 10보다 크고, 20보다 작거나 같은 소수는 4개가 있다. (11, 13, 17, 19) 또, 14보다 크고, 28보다 작거나 같은 소수는 3개가 있다. (17,19, 23)

자연수 n이 주어졌을 때, n보다 크고, 2n보다 작거나 같은 소수의 개수를 구하는 프로그램을 작성하시오. 

 

해결 과정

2부터 그 숫자의 제곱근보다 작은 자연수까지 나누었을 때 나누어 떨어지는 자연수가 없다면 그 숫자는 소수임을 알 수 있다.

import java.util.Scanner; import static java.lang.Math.sqrt; public class Main {     public static void main(String[] args) {         while(true){             int ans = 0;             int check = 0;             Scanner a = new Scanner(System.in);             int n = a.nextInt();             if (n == 0)                 break;             int n2 = n*2;             for (int i = n+1;i<=n2;i++){                 for (int j = 2;j<=sqrt(i);j++){                     if(i < j)                         break;                     if (i%j==0){                         check = 1;                         break;}                 }                 if (check == 0){                     ans++;                     check = 0;                 }             }             System.out.println(ans);         }     } }

변수 i를 통해 n부터 2n 사이의 자연수를,  변수 j를 통해 2부터 i의 제곱근까지의 자연수를 대입해 나누어 떨어지는 j가 있을 경우는 무시, 그 외의 경우를 계산해 출력하도록 하였다. 또한 n의 값을 여러번 반복해서 입력할 수 있되 입력된 n이 0일 경우 프로그램을 종료하도록 하기 위해 while의 조건에는 true로 무한 반복을 구현하였고 while 내부에 입력값이 0인 경우 while문을 탈출하도록 코드를 작성하였다.

 

위의 코드를 제출했을 때 돌아온 답변은 "런타임 에러 (NoSuchElement)"이었다. 원인은 존재하지 않는 것을 가져오려고 할 때 발생하는데, 값을 불러올 때 입력된 데이터가 끝났음에도 EOF로 판단하지 않아 추가로 입력을 받으려고 시도했기에 발생한 에러였다. 따라서 입력이 종료되었기에 불러올 데이터가 없다는 것을 설정해 두는 것이 필요했다.

 

따라서 while문 내부에 추가 입력이 있을 경우 실행될 수 있도록 hasNextInt()를 조건에 추가해 입력이 없다면 불러오지 않도록 코드를 수정하였다.

import java.util.Scanner; import static java.lang.Math.sqrt; public class Main {     public static void main(String[] args) {         Scanner a = new Scanner(System.in);         while(a.hasNextInt()){             int ans = 0;             int check = 0;             int n = a.nextInt();             if (n == 0)                 break;             int n2 = n*2;             for (int i = n+1;i<=n2;i++){                 for (int j = 2;j<=sqrt(i);j++){                     if(i < j)                         break;                     if (i%j==0){                         check = 1;                         break;}                 }                 if (check == 0){                     ans++;                     check = 0;                 }             }             System.out.println(ans);         }     } }

위의 코드를 제출했을 때 런타임 에러는 수정되었지만, 틀렸다는 답변이 돌아왔다. 

코드를 다시 찬찬히 살펴본 결과, for문에서 값이 1로 변경된 변수 check를 다시 사용할 때 초기화하지 않아서 계속 1인 상태로 진행되는 것이 보였다.

 

import java.util.Scanner; import static java.lang.Math.sqrt; public class Main {     public static void main(String[] args) {         Scanner a = new Scanner(System.in);         while(a.hasNextInt()){             int ans = 0;             int check = 0;             int n = a.nextInt();             if (n == 0)                 break;             int n2 = n*2;             for (int i = n+1;i<=n2;i++){                 check = 0;                 for (int j = 2;j<=sqrt(i);j++){                     if (i%j==0){                         check = 1;                         break;}                 }                 if (check == 0){                     ans++;                 }             }             System.out.println(ans);         }     } }

for문 앞에 check 값을 0으로 초기화한 후에는 정답이라는 답변을 받을 수 있었다.