본문 바로가기

백준749

백준 16208 자바 - 귀찮음 (BOJ 16208 JAVA) 문제 : boj16208 1. 우선 그냥 풀어보자. 결국 현재 막대 크기를 x+y로 나눌 수 있을 때, 비용인 xy들의 합을 최소로 하고 싶은 것이다. 그렇다면 수학적으로 최대한 '작은수 x 큰수'가 되도록 하는것이 최소이다. '중간수 x 중간수'일수록 손해이다. 예를들어 현재 길이가 10일 경우 5x5는 25지만 1x9는 9다. 또한 맨 마지막 막대는 비용이 0이므로 (x+0 이므로 xy = 0) 결국 주어진 n개의 쇠막대를 길이가 짧은 순서대로 나누면 된다(그리디 알고리즘). 내 경우엔 어차피 a_i 0) { int cur = Integer.parseInt(st.nextToken()); cnt[cur]++; sum += cur; } long answer = 0; for (int i = 1; i 0) .. 2022. 2. 7.
백준 1590 자바 - 캠프가는 영식 (BOJ 1590 JAVA) 문제 : boj1590 n개의 경우 각각에 대해 만족하는 가장 작은 시각을 찾아보면 된다. n개의 경우 각각에 대해 a가 0부터 C-1까지의 자연수라고 할 때, 다음 식을 통해 나온 값 중 최초로 T 이상의 값이 나오는 경우가 해당 경우의 최소수치이다. n개에 대해 각각 위의 최소수치를 구하고, 그 중 가장 작은 값이 답이다. 이 때 C는 최대 100 이므로 0부터 99까지 전부 다 해봐도 최대 O(NC) 정도의 시간복잡도이므로 전부 다 해보면 된다. 따라서 브루트 포스이며, 최초로 T 이상의 값이 나올 경우 바로 중지하면 되고 추가로 f(a)가 이미 이전에 나온 값보다 큰 경우엔 더이상 볼 필요도 없으므로 백트래킹도 가미하면 좀 더 효율적으로 할 수 있다. 코드에서 while문 내의 's < t'부분이.. 2022. 2. 6.
백준 1287 자바, 파이썬 - 할 수 있다 (BOJ 1287 JAVA, Python) 문제 : boj1287 사실 계산기 구현이니 난이도 때문에 플래라고 보긴 힘든 문제이다. 다만 파이썬으로 날먹하지 않는 이상은 빡구현이 필요하므로 티어가 높아진듯하다(총 1000자리가 입력으로 주어지므로, 500자리 곱하기 500자리와 같은 큰 수 연산이 필요하다). C로는 더 심한 빡구현이 필요해서 도전한 사람이 아직 없는듯하다 ㅋㅋㅋ 1. 우선은 날먹부터 일단 대충 봐도 한방에 계산해주는 무언가가 있다면 날먹이 가능할것처럼 생겼다. 우선은 자바에서 시도를 해봤었다. 아래와 같은 코드인데, 자바스크립트 엔진을 가져와서 자바에서 쓸 수 있다. 그럼 자바스크립트의 eval 함수를 사용해서 바로 계산이 가능하다. ScriptEngineManager scriptEngineManager = new ScriptE.. 2022. 2. 5.
백준 23258 자바 - 밤편지 (BOJ 23258 JAVA) 문제 : boj23258 개인적으로 오늘 푼 플3 문제보다 몇배는 어려웠다. 심지어 플로이드 와샬 알고리즘을 정확히 이해해야 풀 수 있는 문제라고 추천을 받고 풀게되어서 일단 플로이드 와샬을 써야 한다는 점은 알고 풀게 되었는데 그런데도 엄청 해맸다 ㅠ 아무튼 플로이드 와샬을 써보려면 이 문제는 꼭 풀어봐야 할 것 같다. 플로이드 와샬을 이해하는데 도움이 되는 매우 좋은 문제라 생각한다. 1. '2^C 방울 이상 마시면 안된다'의 의미 우선 이 부분부터가 문제였다. 처음엔 뭔가 장난스럽게, 좀 더 복잡하게 보일려고 이렇게 작성했다고 생각했다. 그래서 2^X, 2^C에서 '2^' 부분은 때고 X, C로만 생각했는데 당연히 제대로 답이 안나왔다. 결론적으로 키 아이디어에 해당하는 부분으로 사실 Ce로 가는 .. 2022. 2. 4.
백준 15352 자바 - 욱제와 그의 팬들 (BOJ 15352 JAVA) 문제 : boj15352 1. 우선 '행동 2'만 존재할 경우 어떻게 풀 수 있을지 확인해보자. 입력으로 주어진 N개의 A값들에 대해 좌우로 인접한 항목이 같은 팬클럽 번호라면 그룹을 지어보자. 이 때, union-find를 사용하고 부모가 되는 노드에 차수를 입력해둔다고 한다면 '행동 2'에 대해 O(1)로 부모의 차수를 출력하는 것 만으로 결과를 낼 수 있다. 예를들어 parents[a]에 대해 parents[a] >= 0일 경우 부모의 번호, parents[a] < 0일 경우 부모 중 하나이며, 그 부모에 그룹지어져 있는 노드의 개수라고 하면 예제 입력 1은 다음과 같이 나타낼 수 있다. union-find의 사용방법은 다양한 편이므로, 어쨌든 해당 그룹에 포함된 개수를 한방에 알 수만 있도록 짜면.. 2022. 2. 4.
백준 2688 자바 - 줄어들지 않아 (BOJ 2688 JAVA) 문제 : boj2688 방법 1. dp로 풀기 dp[a][b]를 a개의 수를 가지고 표현할 때 마지막 수가 b일 경우의 수 라고 정의하자. 그럼 이 문제에 대한 dp 점화식은 다음과 같다. 즉, 개수가 하나 더 작은 경우에서(dp[a-1]), 자신보다 작은 경우들에다가 자기 자신을 붙여주면 된다. 예를들어서 현재 b가 3일 경우 001과 113뒤에 3을 붙여 0013, 1133을 만들면 조건을 만족한다. 이 점화실을 a는 1부터 입력받은 n까지, b는 0부터 9까지 진행하면 된다. 그리고 여기에 prefix sum 까지 살짝 넣어주면 시그마를 없애서 시간 복잡도를 좀 더 간소화 시킬 수 있다. 거기에 미리 최대치인 a=64까지 계산해두고, 각 T개의 n개마다 dp[n][0]+dp[n][1]+...+dp[.. 2022. 2. 3.
백준 15992 자바 - 1, 2, 3 더하기 7 (BOJ 15992 JAVA) 문제 : boj15992 1. 단순화 해서 생각해보기 우선 '사용한 수의 개수는 m개' 라는 조건이 없다고 생각해보자. 이 경우 1부터 n까지의 1차원 DP로 풀 수 있다. dp[a]를 a를 1,2,3을 더해서 표현할 수 있는 가지수라고 할 경우, 점화식은 다음과 같을 것이다. 즉, a를 1부터 n까지 증가시키며 다음의 점화식을 적용한 DP를 진행하면 된다. 2. 사용한 수의 개수가 m개 '1'에서 조건이 하나 더 추가되었다. 그러니 2차원 DP로 확장시키면 된다. dp[a][b]를 a를 1,2,3을 b번 더해서 표현할 수 있는 가지수라고 할 경우, 점화식은 다음과 같을 것이다. 마찬가지로 a는 1부터 n까지 증가시키면 되고, 이 때 b는 1부터 min(a, m) 까지 증가시키면서 구하면 된다(그냥 b도.. 2022. 2. 2.
백준 20126 자바 - 교수님의 기말고사 (BOJ 20126 JAVA) 문제 : boj20126 각 시험이 서로 겹치지 않는다는 점 때문에 상당히 쉽게 풀 수 있다. 결국 모든 시험이 겹치지 않으므로, 각 시험의 비어있는 구간이 M 이상인지만 확인하면 된다. 즉, i번째 시험을 arr[i] 라고 한다면, arr[i].x - (arr[i-1].x + arr[i-1].y) 의 값이 M보다 크다면 문제의 조건을 만족하는 시간이 된다. 예를들어 다음의 입력을 봐보자. 3 4 20 3 1 7 5 13 3 위의 그림 중 첫번째 이미지처럼 다른 시험들이 진행될 것이다. 이 때 우리가 확인해야 할 부분은 두번째 이미지의 파란 부분이다. 정렬 후 위에서 제시한 공식대로 진행한다면 어렵지 않게 찾을 수 있다. 답은 16이 될 것이다. 그리고, 그림에서도 나오듯이 주의점은 0-3 구간과 16-.. 2022. 2. 1.
백준 1439 자바 - 뒤집기 (BOJ 1439 JAVA) 문제 : boj1439 아래 에미지에서 첫줄 '11'을 바꿈으로써 그 양옆 '00'들을 한꺼번에 바꿀 수 있는 것 처럼 중간에 있는 무언가를 바꾼다면, 그 다음 더 넓은 지역을 바꾸는데 도움이 된다고 생각할 수 있다. 그래서 어떻게 생각할 지 어렵게 여겨질 수 있다. 하지만 이러한 경우에 어떻게 하든 결국 중간중간 바꾼 것과, 모든 연속된 1 토큰을 0으로 바꾸거나 모든 연속된 0 토큰을 1로 바꾸는 것 중 작은쪽은 횟수가 똑같다. 무슨 말이냐면 그냥 아래와 같이 연속된 1로 구성된 토큰의 개수와, 연속된 0으로 구성된 토큰의 개수 중 작은쪽을 출력하면 끝나는 아주 간단한 문제라는 얘기이다. (만약 '11111' 이런식이었다면 0으로 된 토큰이 0일 것이므로 0이 답) 코드 : github import .. 2022. 1. 31.
백준 18242 자바 - 네모네모 시력검사 (BOJ 18242 JAVA) 문제 : boj18242 몇x몇 짜리 사각형인지만 알면 어차피 정해진 위치에 빈 칸이 있으므로 연산을 통해 알아낼 수 있다. 이에 따라 로직을 다음과 같이 정해서 풀었다. 1. '#'이 처음 나온 줄을 찾는다. 찾은 줄에서 마지막 '#'과 첫번째 '#'의 차이를 통해 길이를 알아내고, 그 중간에 '.'이 있다면 UP 이다. 2. '1'에서 길이를 알아냈으므로 [해당 길이-2/2]만큼은 쓸모없으므로 입력을 버리고, 중앙 행을 찾는다. 여기서 좌측과 우측을 확인하여 LEFT, RIGHT를 알아낼 수 있고 마지막까지 갈 필요없이 아직까지 안나왔다면 DOWN을 출력하면 된다. 코드 : github import java.io.BufferedReader; import java.io.InputStreamReader;.. 2022. 1. 30.

티스토리툴바