백준 알고리즘 9단계 기본 수학2 4948번 문제입니다. Q. 베르트랑 공준은 임의의 자연수 n에 대하여, n보다 크고, 2n보다 작거나 같은 소수는 적어도 하나 존재한다는 내용을 담고 있다. 이 명제는 조제프 베르트랑이 1845년에 추측했고, 파프누티 체비쇼프가 1850년에 증명했다. 자연수 n이 주어졌을 때, n보다 크고, 2n보다 작거나 같은 소수의 개수를 구하는 프로그램을 작성하시오. [입력] - 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 케이스는 n을 포함하는 한 줄로 이루어져 있다. - 입력의 마지막에는 0이 주어진다. [조건] - 각 테스트 케이스에 대해서 n보다 크고 2n보다 작거나 같은 소수의 개수를 출력한다. - 1 ≤ n ≤ 123456 풀이 이 문제 역시 소수의 연장선에 ..

백준 알고리즘 9단계 기본 수학2 11653번 문제입니다. Q. 정수 N이 주어졌을 때, 소인수분해하는 프로그램을 작성하시오. [입력] - 첫째 줄에 정수 N이 주어진다. [조건] - 1 ≤ N ≤ 10000000 - N의 소인수분해 결과를 한 줄에 하나씩 오름차순으로 출력한다. N이 1인 경우 아무것도 출력하지 않는다. 풀이 소인수분해는 1보다 큰 자연수를 소수인 인수들만의 곱으로 나타내는 것이다. Ex) 72 = 2 * 2 * 2 * 3 * 3 82 = 2 * 41 125 = 5 * 5 * 5 28 = 2 * 2 * 7 소인수분해 결과를 오름차순으로 출력하면 되는 문제이기 때문에 소수 중 가장 작은 수인 2부터 나누기 시작해서 0으로 떨어지지 않는 경우는 증감시키고 0으로 떨어지는 경우는 반복을 해주..

백준 알고리즘 9단계 기본 수학2 2581번 문제입니다. Q. 자연수 M과 N이 주어질 때 M이상 N이하의 자연수 중 소수인 것을 모두 골라 이들 소수의 합과 최솟값을 찾는 프로그램을 작성하시오. [입력] - 첫째 줄에 M이, 둘째 줄에 N이 주어진다. [조건] - M과 N은 10000이하의 자연수이며, M은 N보다 작거나 같다. - M이상 N이하의 자연수 중 소수인 것을 모두 찾아 첫째 줄에 그 합을, 둘째 줄에 그 중 최솟값을 출력한다. - M이상 N이하의 자연수 중 소수가 없을 경우는 첫째 줄에 -1을 출력한다. 풀이 이전 문제(1978번)의 연장선으로 이전 문제가 테스트 개수만큼 입력받은 수의 소수를 구했다면 이 문제는 입력받은 M, N 사이의 소수를 구해야했다. 소수를 구하는 방식은 동일하게 사..

백준 알고리즘 9단계 기본 수학2 1978번 문제입니다. Q. 주어진 수 N개 중에서 소수가 몇 개인지 찾아서 출력하는 프로그램을 작성하시오. [입력] - 첫 줄에 수의 개수 N이 주어진다. - 둘째 줄에 N개의 수가 주어진다. [조건] - N은 100이하이다. - N개의 수는 1000이하의 자연수이다. 풀이 소수는 1보다 큰 자연수 중 1과 자기 자신만을 약수로 갖는 수를 말한다. 이 문제는 반복문을 돌려 자신 이외의 수로 떨어지는 경우를 체크하는 방식으로 풀 수 있었다. 소스 package com.baek.algo.step09; import java.util.Scanner; public class Q1978 { public static void main(String[] args) { Scanner s..

백준 알고리즘 8단계 기본 수학1 10757번 문제입니다. Q. 두 정수 A와 B를 입력받은 다음, A+B를 출력하는 프로그램을 작성하시오. [입력] - 첫째 줄에 A와 B가 주어진다. [조건] - 0 < A,B < 10의 10000승 Ex) 9223372036854775807 + 9223372036854775808 = 18446744073709551615 풀이 이 문제는 정수형 타입의 범위를 벗어날 경우 어떻게 계산을 할 것인지에 대한 문제였다. long타입 범위는 -9223372036854775808 ~ 9223372036854775807로 예제와 같이 두 정수를 더하는 경우 범위를 넘게 된다. 가장 먼저 든 생각은 입력받은 숫자를 문자열로 받아 각각의 자리수 합을 더해 총 합을 구하는 것이었다. 입..

백준 알고리즘 8단계 기본 수학1 2775번 문제입니다. Q. 아래 조건과 같은 아파트가 있을 때, k층 n호에는 몇 명이 살고 있는지 출력하는 프로그램을 작성하시오. [입력] - 첫 번째 줄에 테스트 케이스 T가 주어진다. - 각각의 케이스마다 첫 번째 줄에 정수 K, 두 번째 줄에 정수 N이 주어진다. [조건] - 1 ≤ K, N ≤ 14 - K층 N호에 살려면 자신의 아래(K-1)층의 1호부터 N호까지 사람들의 수의 합만큼 사람들이 살아야한다. - 아파트는 0층부터 있고 각층은 1호부터 있으며 0층의 i호에는 i명이 산다. 풀이 문제를 풀기 위해 조건에 따라 아파트를 그려봤다. 아파트는 0층부터 있으며, 0층은 숫자가 1부터 +1씩 증가한다. 조건에 따라 K층 N호에 거주하는 사람 수는 K-1층의 ..

백준 알고리즘 8단계 기본 수학1 2839번 문제입니다. Q. 설탕을 정확하게 N킬로그램 배달해야 할 때, 봉지 몇 개를 가져가면 되는지 그 수를 구하는 프로그램을 작성하시오. [입력] - 첫째 줄에 N이 주어진다. [조건] - 3 ≤ N ≤ 5000 - 봉지는 3킬로그램 봉지와 5킬로그램 봉지가 있다. - 봉지의 최소 개수를 출력한다. 만약 정확하게 N킬로그램을 만들 수 없다면 -1을 출력한다. Ex) 18킬로그램 설탕을 배달해야 할 때, 3킬로그램 봉지 6개를 가져가도 되지만 5킬로그램 3개와 3킬로그램 1개를 배달하면 더 적은 개수의 봉지를 배달할 수 있다. 풀이 일단 봉지를 가장 적게 가져가기 위해서는 당연하게도 3킬로그램 봉지보다는 5킬로그램 봉지를 최대한 사용해야한다. 먼저, 테스트 케이스를 ..

백준 알고리즘 8단계 기본 수학1 10250번 문제입니다. Q. ACM 호텔 매니저 지우는 손님이 도착하는 대로 빈 방을 배정하고 있다. 고객 설문조사에 따르면 손님들은 호텔 정문으로부터 걸어서 가장 짧은 거리에 있는 방을 선호한다고 한다. 호텔 정문은 일층 엘리베이터 바로 앞에 있는데, 정문에서 엘리베이터까지의 거리는 무시한다. 설문조사 결과 대로 호텔 정문으로부터 걷는 거리가 가장 짧도록 방을 배정하는 프로그램을 작성하시오. [입력] - 첫 줄에 테스트 데이터 개수 T가 주어진다. - 호텔의 층 수, 각 층의 방 수, 몇 번째 손님인지를 나타내는 세 정수 H, W, N이 주어진다. [조건] - 1 ≤ H, W ≤ 99, 1 ≤ N ≤ H × W - 호텔은 직사각형 모양이고 각 층에 W 개의 방이 있는..