본문 바로가기

PS818

CodeForces 4A - Watermelon (Java) 문제 : https://codeforces.com/contest/4/problem/A 수박을 짝수 무게의 두 조각으로 나눌 수 있어야 한다. 짝수 + 짝수 = 짝수 이고, 짝수는 2 이상이어야 하므로 입력으로 들어온 'w'가 4 이상의 짝수인지만 확인하면 된다. 코드 : github import java.io.BufferedReader; import java.io.InputStreamReader; public class Main { public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int w = Integer.parseI.. 2021. 11. 27.
백준 2697 자바 - 다음수 구하기 (BOJ 2697 JAVA) 문제 : https://www.acmicpc.net/problem/2697 A와 같은 구성에 A보다 큰 수 중 가장 작은 수는 그리디로 해결할 수 있다. 사실 이건 그리디야! 하고 푼건 아니고, 규칙을 찾고보니 그리디 스러운 규칙이었다.ㅋㅋ 1. 수를 뒤에서부터 한 자리씩 보면서, 처음으로 수가 이전보다 작아진 지점을 찾는다. 해당 지점을 T라고 하겠다. 2. T위치 이전은 그대로 출력한다. 그리고 T 위치를 포함해, 그 이후 위치에 대해 나왔던 숫자들을 몇번씩 나왔는지 카운팅한다. 3. T 이후의 위치에 있는 수 중, T에 해당하는 수보다 크면서 가장 작은 수를 찾아 T의 위치에 넣는다. 4. 카운팅해둔 값을 가지고, 작은 숫자부터 차례대로 카운팅값 횟수만큼 출력한다. 설명하기가 애매하니 예시를 들어 .. 2021. 11. 26.
백준 1622 자바 - 공통 순열 (BOJ 1622 JAVA) 문제 : https://www.acmicpc.net/problem/1622 중요한건 2개의 문자열에서 각각의 문자열에 포함된 알파벳의 갯수이다. 예를들어 다음을 보자. S1 : accaab S2 : cccabbb S1은 a:3, b:1, c:2 S2는 a:1, b:3, c:3 이다. 이렇게 카운팅만 할 수 있다면, 사전순으로 가장 빠르면서 문제에서 제시된 출력은 a,b,c,d,...,z 까지 세어둔 수를 확인하면서 둘 중 작은 개수만큼 출력하면 된다. 위를 예로들면 a : 3과 1중 작은거, b : 1과 3중 작은거, c : 2와 3중 작은거. 따라서 a를 1번, b를 1번, c를 2번 출력하면 되므로 답은 abcc가 된다. 코드 : https://github.com/NaHwaSa/BOJ_BaekjunO.. 2021. 11. 25.
백준 11969 자바 - Breed Counting (BOJ 11969 JAVA) 문제 : https://www.acmicpc.net/problem/11969 breed 1,2,3에 각각 범위 내에 포함된 카운팅값의 합을 출력하면 된다. prefix sum을 활용하면 풀 수 있다. breed1,2,3로 나누어서 카운팅한 값의 누적합을 저장하는 방식으로 진행하면 된다. 예제 입력1에 대해 그려보면 다음과 같다. N번 소에 대해 breed1,2,3를 사용했음을 기입한 것이다. 이걸 breed 1,2,3에 대해 각각 누적합을 구해보면 다음과 같다. 이렇게 전처리로 누적합을 구해두고, 각 쿼리의 a, b값에 대해 범위내의 합계를 출력해주면 된다. 예를들어 a=2, b=4라면 breed1의 경우 breed1[b] - breed1[a-1] = 2 - 0 = 2, breed2의 경우 마찬가지로 1.. 2021. 11. 24.
백준 15725 자바 - 다항함수의 미분 (BOJ 15725 JAVA) 문제 : https://www.acmicpc.net/problem/15725 문자열 파싱 문제이다. 다음의 경우에 대해서 case work를 진행하면 쉽게 풀 수 있다. 1. x+n, n+x와 같은 형태(n은 아예 없이 "x"와 같은 경우도 포함) -> 1 출력 2. -x+n, n-x와 같은 형태 -> -1 출력 3. x없이 n과 같은 형태 -> 1차항이 아예 없으므로 0 (아마 여기서 많이들 틀릴 듯) 4. ax+n, n+ax의 형태 -> a 5. -ax+n, n-ax의 형태 -> -a 적절히 위의 모든 경우를 찾아내면 된다. 코드 : https://github.com/NaHwaSa/BOJ_BaekjunOnlineJudge/blob/master/15700/BOJ_15725.java import java.. 2021. 11. 24.
백준 4781 자바 - 사탕 가게 (BOJ 4781 JAVA) 문제 : https://www.acmicpc.net/problem/4781 유명한 DP 활용 문제 유형인 냅색(knapsack) 문제이다. '각 사탕의 개수는 매우 많기 때문에, 원하는 만큼 사탕을 구매할 수 있다.'라는 부분 때문에 냅색에서 난이도가 좀 낮춰지지만, 가격이 실수라서 난이도가 다시 높아진다 ㅋㅋㅋ 결국 실수만 잘 처리할 수 있으면 DP를 사용해 풀 수 있다. 그래도 양심이 있는지 소수점 두번째 자리까지만 주어지고, 최대 100.00 이라서 그냥 100을 곱해서 처리하면 된다. 소수점을 처리할 방법들중 몇가지는 다음과 같다. 1. 주어진 실수에 100을 곱한다. -> 주의점은 입력받은 실수에 100을 곱한 후 +0.1 정도를 해줘서 소수점 오차를 없앤 후 int형으로 형변환 해야한다. 안전.. 2021. 11. 23.
백준 8598 자바 - Zając (BOJ 8598 JAVA) 문제 : https://www.acmicpc.net/problem/8598 일단은 무지성으로 BFS 돌리면 되는 문제긴 하다. 그래서 딱히 안적을까 했는데, 언어가 이상하다보니 번역기 돌려도 놓칠만한 부분 적어봄. 'x'는 못감. 'z'가 시작점. 'n'이 도착지점. 다만 문제 특성상 n에서 출발해서 z에 도착해도 상관은 없다. 그리고 제일 중요한 부분은 길이 존재하지 않을 경우 "NIE"를 출력해야 한다. 코드 : https://github.com/NaHwaSa/BOJ_BaekjunOnlineJudge/blob/master/08500/BOJ_8598.java import java.io.DataInputStream; import java.io.IOException; import java.sql.Array.. 2021. 11. 23.
백준 1747 자바 - 소수&팰린드롬 (BOJ 1747 JAVA) 문제 : https://www.acmicpc.net/problem/1747 풀이1 다소 어려워보일 수 있으나, 문제에서 원하는 부분을 순서대로 구현하면 어렵지 않다. 1. 소수를 알 수 있어야 한다. 이때, N은 최대 100만인데 문제에서 요구하는 것은 N 보다 '큰거나 같은 수'중 소수이면서 팰린드롬인 수 이므로 100만까지만 소수를 구해서는 안된다. 약간 범위를 늘려봐서 확인해보면 되는데, 결론적으로 1,003,001 까지 확인해보면 모든 입력에 대해 만족할 수 있다. 소수를 구하는 것은 에라토스테네스의 체를 사용하면 된다. 2. 소수 중 팰린드롬인 수를 알 수 있어야 한다. 숫자 자체로 맨앞과 맨뒤 문자열을 비교하며 중간까지 와도 되는데, 중간에서 멈추기가 좀 어렵다. 어차피 최대 100만 근처의 .. 2021. 11. 23.
백준 5966 자바 - Cow Cotillion (BOJ 5966 JAVA) 문제 : https://www.acmicpc.net/problem/5966 '>'와 ''를 넣고, ''와 ''와 '') cnt1++; else cnt2++; if (cnt2>cnt1) return false; } if (cnt1!=cnt2) return false; return true; } private void solution() throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int n = Integer.parseInt(br.readLine()); StringBuilder sb = new StringBuilder(); while (n-->0) { StringTokenizer st =.. 2021. 11. 23.
백준 21187 자바 - Pulling Their Weight (BOJ 21187 JAVA) 문제 : https://www.acmicpc.net/problem/21187 뭔가 복잡해보이는데, 좀 정리해보면 그냥 brute force로 해결 가능한 문제이다. 1 최대 10^5개의 동물의 무게가 주어진다. 그리고 각 무게는 2만 이하이므로, 전부 더해도 20억 이하로 Integer로 표현 가능한 수치이다. 2 사실 동물이 몇마리가 주어지든 상관없고 중요한 데이터는 결국 '1~20,000 사이의 각 무게를 가진 동물이 각 몇마리씩 존재하는지' 이다. 3 정렬이 필요할것같이 생겼지만, 사실 무게가 2만 이하라서 배열에 카운팅한다면 정렬은 따로 필요 없다. 다음의 입력을 보자. 6 5 7 5 5 3 4 위 입력을 배열로 카운팅해보면 다음과 같다. 4 그럼 이제 index 기준으로 1부터 20000까지를 .. 2021. 11. 22.

티스토리툴바