본문 바로가기

BOJ737

백준 9753 자바 - 짝 곱 (BOJ 9753 JAVA) 문제 : boj9753 100000일 때 100001이 답이란걸 문제 예시에서 보여줬으므로 사실 100000이하의 소수 곱에 대해서만 신경쓰면 된다. 그리고 어차피 가장 작은 소수가 2 이므로 50000까지만 보면 된다. 따라서 5만 이하의 모든 소수를 우선 에라토스테네서의 체로 구한다. 그리고 소수의 곱을 모든 쌍을 보면서 모두 구한다. 이 때 10만이 넘어간다면 제외해도 된다. 구한 값은 어차피 10만까지만 알면 되므로 배열에 넣어도 되고, 내 경우엔 더 큰 수를 빨리 구해보려고 TreeSet에 넣었다. 이후 하나씩 입력받으면서 TreeSet의 ceiling을 출력하면 된다. '2'의 과정을 배열에 했다면 입력받은 값 이상을 순회하며 가장 작은 소수를 출력하면 된다. 코드 : github import.. 2022. 1. 18.
백준 10373 자바 - Buffcraft (BOJ 10373 JAVA) 문제 : boj10373 1. 문제 정의 상당히 문제가 불친절하다. 예제라도 의미 있을 예제를 들어주면 좋을텐데 ㅡㅡ; 상당히 별로인 문제이다. 1.1 'The following line must contain n different numbers', 'The last line of the output must contain m different numbers' 에 따라 출력을 해줘야 하는데, 그럼 following line이 0이라 출력할 게 없으면 줄을 띄워야 되나 말아야 하나라는 문제점이 있다(second, third line이라고 하던지.. 저렇게 하면 사실 following line이 last line이 되기도 하므로 애매하다.). 원래 문제대로라면 줄을 띄워야 맞지만(해당 대회 문제 채점 데이터.. 2022. 1. 17.
백준 8807 자바 - Przedziały (BOJ 8807 JAVA) 문제 : boj8807 1. 다음과 같은 입력을 생각해보자. 1 5 1 2 2 2 3 5 7 8 10 10 이 문제의 경우 만약 모든 범위를 한 선에 겹쳐그릴 수 있다면 쉽게 답을 구할 수 있을 것이다. 그럼 어떻게 각 범위를 합칠 수 있을지 생각해보면 된다. 우선 가장 간단한 방식으로, 모든 범위에 해당하는 배열을 만들고 입력을 받으며 범위를 채운 후, 마지막에 모든 범위에 대해 확인해서 개수를 세는걸 생각할 수 있다. 다만 이 문제의 경우 이렇게되면 모든 범위가 -10억~+10억이 되므로 모든 범위 확인만해도 대략 20초정도 걸린다. 2. 다른 방법을 생각해보자. 사실 각 A,B에 대해 범위를 순회만 해도 최대 20억번 해야하므로 시간초과가 확실하다. 따라서 아예 다른 방식으로 생각해봐야 한다. OR.. 2022. 1. 16.
백준 3518 자바 - 공백왕 빈-칸 (BOJ 3518 JAVA) 문제 : boj3518 문제는 참 직관적이고 간단한 구현문제인데, 생각보다 꾸현이 까다롭긴 하다. 나온 설명대로 문자열 파싱만 잘 하면 되서 딱히 알고리즘적으로 설명할 건 없다. 주의점은 좀 있다. 첫째로 다음과 같은 경우를 보자. abc def zzz ggg 이미 문제에서 제시된 방식되로 잘 배치되어 있지만, '사전순으로 가장 앞서는 것'을 출력해야 하므로 공백을 1칸으로 줄여야 한다. abc def zzz ggg 두번째로 각 출력문의 마지막에 추가 공백이 있으면 안된다. 딱 출력해야 되는 문장에서 추가 공백 없이 그것만 출력해야 된다. 그 이외에는 백준에서 '출력 형식이 잘못되었습니다'이 뜬다. 코드 : github import java.io.BufferedReader; import java.io.I.. 2022. 1. 15.
백준 17245 자바 - 히스토그램 (BOJ 17245 JAVA) 문제 : boj17245 일단 단순화 시켜서 생각해보기 위해 좌측부터 우측으로 점차 증가하는 형태와 점차 감소하는 형태를 나눠서 생각해봤다. 1. 우선 높이(h)가 같거나 증가하는 경우이다. 이전과 비교해서 값이 같거나 증가하고 있다면, 아직까지는 넓이를 계산하는 것이 의미가 없다. n개를 모두 입력받았거나, 이후 감소하는 구간을 만나기 전까지는 넓이를 계산하지 않고 있다가 맨 마지막 지점에서만 계산해주면 된다. 직관적으로 맨 마지막 지점을 포함한 상태에서 다음과 같이 이전 높이들을 확인하면 될 것임을 예상할 수 있다. 즉, 높이가 동일하거나 증가하는 경우 맨 마지막 지점에서 이전 지점 모두 중 의미가 있는 넓이는 모두 계산할 수 있다. 2. 다음은 높이(h)가 감소하는 경우이다. 이번엔 좌측에서 우측으.. 2022. 1. 13.
백준 4386 자바 - 별자리 만들기 (BOJ 4386 JAVA) 문제 : boj4386 1. 모든 별을 이어야하고, 최소 비용을 구해야 한다. 따라서 N개의 정점(별)에 대해 이은 간선이 N-1개(모든 정점을 포함하려면 최소 N-1개의 간선이 필요하고, 최소비용을 위해서는 거기서 하나라도 간선이 추가되선 안되므로) 이어야만 모든 별을 이으면서 최소 비용이 가능하다. 따라서 Spanning Tree를 구성해야 하고, 최소 비용이어야 하므로 MST (Minimum Spanning Tree)를 구하는 문제임을 알 수 있다. 후보군이 될 간선은 N개에 대해 다른 N-1개 모두로의 간선이므로 간선은 총 N*(N-1)개 존재할 수 있다. 이 중 N-1개를 골라 MST를 만들었을 때의 최소 비용이 답이다. 2. 대표적인 MST 알고리즘에는 Prim과 Kruscal이 있다. 이 문.. 2022. 1. 12.
백준 14248 자바 - 점프 점프 (BOJ 14248 JAVA) 문제 : boj14248 문제 자체의 정의에 따라 i번째 정점에서 i-Ai, i+Ai 로의 간선이 생긴다. 이에 대해 단순히 방문 가능한 위치만 찾으면 되므로 dfs 혹은 bfs로 더이상 진행 불가할때까지 진행해보면서 방문한 곳의 개수를 세면 된다. 코드 : github import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main { boolean[] v; int cnt = 0, n; int[] arr; private void dfs(int s) { if (sn||v[s]) return; v[s] = true; cnt++; dfs(s+arr[s]); dfs(.. 2022. 1. 11.
백준 11060 자바 - 점프 점프 (BOJ 11060 JAVA) 문제 : boj11060 N이 1000까지이고, Ai가 최대 100이라 대충 돌려도 O(NA = 100000) 이라 널널한 문제이다. 가장 좌측지점부터 시작해서 dp 개념을 살짝 섞은 브루트포스로 풀면 된다. 각 입력값에서 갈 수 있는 모든 곳을 가보면서 최소로 갈 수 있는 수치로 갱신해가면 된다. dp[x]는 x위치까지 갈 수 있는 최소 점프 횟수가 된다. 점화식은 Ai에서 i=x에서 시작해 우측으로 이동한 경우이고 현재 y (x+1 2022. 1. 10.
백준 9847 자바 - 4SUM (BOJ 9847 JAVA) 문제 : boj9847 1. Brute Force로 가능한가? 4개의 수의 합이 0이 되는 경우를 찾아야 한다. 제일 간단하게 생각해보면 모든 쌍을 보면 된다. 이 경우 O(500^4) 이므로 유효한 시간 내에 찾을 수 없다. 2. 문제를 단순화 해보자 그럼 우선 문제를 단순화해서 생각해보자. 세트가 2개만 존재한다고 생각해보자(각 세트에 들어간 수는 N개). 그럼 각 세트에서 하나씩 골라서 2개의 수의 합은 어떻게 찾을 수 있을까? 모든 경우를 보는 O(N^2)보다 더 빠른 방법이 있을까? 두 세트가 X와 Y라고 한다면, X의 수를 정렬한 후 Y의 모든 수를 순회하면서 X에 대해 이분탐색으로 합이 0이 되는 경우를 찾을 수 있을 것이다. 그럼 O(NlogN[정렬] + N[순회]*logN[이분탐색]) 정.. 2022. 1. 8.
백준 20949 자바 - 효정과 새 모니터 (BOJ 20949 JAVA) 문제 : boj20949 원하는 방식으로 정렬하는 방법만 알면 쉽게 풀 수 있는 문제이다. 이 문제의 경우 쿼리로 따지면 ORDER BY [W^2+H^2 값] DESC, IDX ASC 인 셈이다. 이 때 W^2+H^2은 W와 H가 모두 최대 3만이므로 두 합은 최대 18억으로, int형으로 표현 가능한 수치이다. 당연하게도 문제에서 square root가 있다고 루트 씌우고 계산하면 소수점 오차때문에 틀릴 수 있다. 코드 : github import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.Arrays; import java.util.StringTokenizer; class Monitor implements Co.. 2022. 1. 6.

티스토리툴바