본문 바로가기

PS/BOJ757

백준 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.
백준 2912 자바 - 백설공주와 난쟁이 (BOJ 2912 JAVA) 문제 : https://www.acmicpc.net/problem/2912 1. 기본적인 아이디어는 각 쿼리의 [a, b] 구간에 대해 매번 [a, b] 전체를 확인하지 않고, 이전에 확인했던 구간과 겹치는 구간은 제외하고 확인하는 것이다. 예를들어 이전에 확인했던 구간이 [1, 100]이고 이번에 확인할 구간이 [4, 95]라고 해보자. 이 때, [1, 100] 구간을 전부 확인하면 100번 + [4, 95] 구간을 전부 확인하면 92번 봐야 한다. 그럼 192번 동작해야 한다. 하지만 [1, 100] 구간의 결과에서 [1, 3] 구간을 빼고, [96, 100] 구간을 빼면 [4, 95] 구간 전체를 본 것과 동일한 결과를 얻을 수 있다. 이 경우 108번만 동작하면 된다. 2. update가 없는 쿼.. 2021. 11. 20.
백준 14897 자바 - 서로 다른 수와 쿼리 1 (BOJ 14897 JAVA) 문제 : https://www.acmicpc.net/problem/14897 확실히 나한테 아직 플래수준은 어려운것같다. 아예 모르는 알고리즘 지식을 요구하는 문제가 아닌이상 꾸역꾸역 풀긴 하는 편인데 사실 이런게 CP에서 나왔다고 치면 시간내에 절대 못푼다. 못해도 1시간 이상은 걸리는 것 같다. 오답률도 높은편 ㅠ 뭐 꾸준히 하다보면 언젠가 플래수준도 쉽게 풀겠지! 생각 과정 풀이만 보려면 아래로 쭉 내려서 '풀이 정리'로 바로 가시면 됩니다. 1. 우선 문제에서 바로바로 생각나는걸 정리했다. - 업데이트가 없는 쿼리 이므로, 쿼리 순서를 마음대로 처리해도 된다. (오프라인 쿼리) - N이 최대 100만, 배열에 포함된 수는 최대 10억이다. 이 때, 문제에서 묻는건 서로 다른 수의 개수이므로 배열에.. 2021. 11. 19.

티스토리툴바