본문 바로가기

Algorithm

 (252)
[백준] 1929 : 소수 구하기 JAVA 풀이 우선 구현을 해봤는데..계속 출력 초과나 오답이라고 나와서 결국 서치를 해봤다. 1. 소수인지 판별하고 싶은 범위만큼 배열을 만든다.(기본값 false) 2. 2부터 특정 수의 배수인 수들을 지운다.(자기자신은 지우지 않음) 3. 배열에서 false인 값들을 출력한다. import java.io.InputStreamReader; import java.io.BufferedReader; import java.io.IOException; import java.util.StringTokenizer; public class Main{ public static boolean[] primeList; // 소수인지 판별하는 배열 생성. 기본값 false public static void main(String[] arg..
[백준] 11653 : 소인수분해 JAVA 풀이 소인수분해란 1보다 큰 자연수를 소수들만의 곱으로 나타내는 것이다. 입력받은 수가 소수로 나눠떨어질 때마다 그 소수를 출력해주면 되는데, 처음엔 2부터 입력받은 수 사이의 소수를 다 구한다음 그 소수로 나눠봐야 하나??싶었다. 하지만 좀 더 고민해보니 그럴 필요가 없다는 걸 알게 됐다. 소수가 아닌 수는 합성수인데, 합성수는 둘 이상의 소수를 곱한 수이므로 소수들로 쪼갤 수 있다. 그러니 2부터(1은 소수가 아니니 제외) 입력받은 수까지 1씩 증가시켜나가면서 입력받은 수를 나누다보면 자연스럽게 소수들로 쪼개지는 것이다. import java.io.InputStreamReader; import java.io.BufferedReader; import java.io.IOException; public clas..
[백준] 2581 : 소수 JAVA 풀이 1. M과 N을 입력받는다. 2. M이상 N이하의 수에 대해 그 수가 소수인지 검사한다. 3. 소수라면 소수의 합을 구하는 변수 sum에 더한다. 그리고 소수값 중 최솟값을 찾는다. 4. M이상 N이하의 값 중 소수가 없다면 sum이 0일 테니 이 경우에는 -1을 출력한다. 5. sum이 0이 아닌 경우(소수가 존재하는 경우) 소수의 합과 최솟값을 출력한다. import java.io.InputStreamReader; import java.io.BufferedReader; import java.io.IOException; public class Main{ public static void main(String[] args)throws IOException{ BufferedReader br = new Bu..
[백준] 1978 : 소수 찾기 JAVA 풀이 소수는 1과 자기자신 외의 약수를 가지지 않는 수이다. 어떤 수 n이 있을 때, n을 1부터 n으로 나누었을 때 나눠떨어지는 수가 단 2개여야 한다는 뜻이다. 따라서 입력될 숫자의 개수인 N을 입력받고 N개만큼의 숫자를 입력받은 뒤에 그 수의 약수가 2개일 때마다 소수의 개수를 증가시켜줬다. import java.io.InputStreamReader; import java.io.BufferedReader; import java.io.IOException; import java.util.StringTokenizer; public class Main{ public static void main(String[] args)throws IOException{ BufferedReader br = new Buffer..
[백준] 2775 : 부녀회장이 될 테야 JAVA 풀이 1. 0층에 사는 사람 수를 배열에 저장함 2. 1의 배열을 이용해서 1층의 n호실까지 그 방에 살기 위해 데려와야 하는 사람의 수를 구해서 배열에 새로 저장함 3. 업데이트된 배열을 이용해 k-1층까지 반복. 이런 방식으로 문제를 해결했다. 부족한 설명이지만, 문제에 주어진 예제 입력인 k = 1, n = 3으로 예를 들어보겠다. 맨 처음 0층에 사는 사람 수를 저장하고 있는 배열은 이렇다. { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 0} (문제에서 1호부터 시작한다고 했으니 인덱스 0번을 1호로 삼았다.) 이것을 이용해 1층의 3호실까지 살기 위해서 필요한 사람 수를 구해서 다시 배열에 저장한다. { 1, 1+2, 1+2+3, .....} n호실 이후는 필..
[백준] 2839 : 설탕 배달 JAVA 풀이 이 문제에서는 봉지의 최소 개수를 찾아야 하는데, 가능한 한 5kg짜리 봉지를 가져가야 한다는 것이다. 입력받은 N이 5로 나눠떨어지면 바로 N을 5로 나눈 몫을 출력하면 된다. 그렇지 않은 경우에는 3kg 봉지를 하나씩 추가하면서, 남은 무게가 5로 나눠떨어지는지 체크했다. import java.io.InputStreamReader; import java.io.BufferedReader; import java.io.IOException; public class Main{ public static void main(String[] args)throws IOException{ BufferedReader br = new BufferedReader(new InputStreamReader(System.in));..
[백준] 10250 : ACM 호텔 JAVA 풀이 문제의 길이를 보고 좀 겁먹었는데 의외로 금방 풀 수 있었다. 101 - 201 - 301 - 401 - 501 - 601 - 102 - 202 - 302 - 402 - 502 - 602 같은 순서로 방이 배정되는데 테스트케이스의 개수를 T 건물의 층수를 H 한 층의 객실수를 W 방을 배정해야 할 손님의 번호를 N 라고 했을 때 층수는 N % H라는 걸 알 수 있다. 이때 주의해야 할 점이 있는데 N이 12고 H가 6이라면 원래대로라면 6층에 배정이되어야 하는데 나머지가 0이라서 0층에 배정되는 문제가 발생한다. 필자도 채점을 해보니 자꾸 오답이 나와서 왜인지 고민을 해보니 이 부분을 처리하지 않은 게 문제였다. 아무튼 N이 H로 나눠떨어질 때에는 H 그 자체가 층수가 된다. 이제 호수를 구해보자. 호수..
[백준] 2869 : 달팽이는 올라가고 싶다 JAVA 풀이 시간제한이 있다는 걸 보긴 했지만 우선 반복문으로 풀어보았다. 결과는 당연히 시간초과였고 식을 대체 어떻게 찾아야 하나 고민을 해봤다. V까지 올라가는 데에 필요한 날짜를 N이라고 했을 때 1일차 낮 : A 1일차 밤 : A - B 2일차 낮 : A - B + A 2일차 밤 : A - B + A -B 이런식으로 진행이 되는데 중요한 점은 이미 V에 도달했다면 더 미끄러지지 않는다는 점이다. 낮과 밤이 한 세트가 아니라는 뜻이니, 낮에 V에 도달했는지 검사하고 그렇지 않으면 하루를 더 추가하기로 했다. 다시 낮의 식을 보면 N*A - (N-1)*B 로 나타낼 수 있는데, 이것이 V 이상이 될 때의 N을 찾아야 하는 문제인 것이다. 이를 식으로 나타내면 V = N*A - N*B + B V - B = N(A-..

티스토리툴바