본문 바로가기

BOJ735

백준 20159 자바 - 동작 그만. 밑장 빼기냐? (BOJ 20159 JAVA) 문제 : boj20159 1. 정훈이가 받을 차례에 밑장빼기 한 경우 기본 아이디어는 직접 밑장빼기를 할 때 어떤 카드를 주게되는지 그려보면서 해보면 어렵지 않게 찾을 수 있다. 예제 입력 1 (3 2 5 2 1 3)을 홀수번째 카드(원래 정훈이가 받을 카드)와 짝수번째 카드(원래 상대방이 받을 카드)로 나눠서 그려보자. 그럼 밑장빼기를 하지 않는다면 다음과 같이 3, 5, 1을 받게 된다. 그럼 5번을 받을 차례 때 밑장빼기를 하면 어떻게 될까? '5'를 받을 차례에 짝수번째의 마지막에 있는 '3'을 받고, 이후 순서가 변경되면서 짝수번째를 정훈이가 받게 된다. 따라서 밑장빼기를 한 이후로는 짝수번째 카드를 받게 된다. 이런식으로 모든 경우를 다 그려보면 다음과 같다. 2. 정훈이가 상대방한테 밑장을 .. 2021. 12. 20.
백준 2806 자바 - DNA 발견 (BOJ 2806 JAVA) 문제 : boj2806 1. 문자를 하나씩 보면서 전부 A, 혹은 B로 변경해 나간다고 생각해보자. 그렇다면 8가지 경우가 나온다. case1. 현재 문자는 A, 이전까지 전부 A 였음, 전부 A로 유지할 것임 -> 이전 상태에 그냥 A를 붙이면 된다. (돌연변이 +0) case2. 현재 문자는 A, 이전까지 전부 A 였음, 전부 B로 유지할 것임 -> 이전 상태에 그냥 A를 붙인 후, 전체를 B로 변경한다. (돌연변이 +1) case3. 현재 문자는 A, 이전까지 전부 B 였음, 전부 A로 유지할 것임 -> 이전 상태 전체를 A로 변경하고 A를 붙인다. (돌연변이 +1) case4. 현재 문자는 A, 이전까지 전부 B 였음, 전부 B로 유지할 것임 -> 현재 문자를 B로 변경해서 붙인다. (돌연변이 +.. 2021. 12. 19.
백준 2636 자바 - 치즈 (BOJ 2636 JAVA) 문제 : boj2636 1. 우선 '치즈의 구멍 속에는 공기가 없지만 구멍을 둘러싼 치즈가 녹아서 구멍이 열리면 구멍 속으로 공기가 들어가게 된다.' 부분부터 생각해보자. 1로 막혀있는 0 부분은 공기로 치지 않는다는 의미로, 이 조건에 따라 단순히 '0'과 인접한 '1'만 찾아선 안된다. 탐색에 익숙하지 않다면 아이디어를 떠올리기 힘들 수 있다. 이 문제의 경우 외부 공기에서부터 탐색을 시작하면 치즈로 둘러쌓인 내부는 보지 않을 수 있다. 그리고 이 문제는 친절하게 판의 가장자리에는 치즈가 놓여있지 않다고 한다. 그러니 단순하게 0,0 지점에서 시작하면 언제나 외부 공기에서 시작함을 보장할 수 있다. 따라서 모든 치즈가 사라질 때 까지, 0,0 부터 시작하는 bfs 혹은 dfs를 계속 반복하고, 그때마.. 2021. 12. 18.
백준 1132 자바 - 합 (BOJ 1132 JAVA) 문제 : boj1132 1. 쉽게 생각할 수 있는 방식인 단순히 자리수가 높다고 높은 수를 주는 방식은 쉽게 반례를 찾을 수 있다. AB B B B B B B B B B B 와 같은 입력에 대해 단순히 A가 자리수가 크다고 9를 주면 안된다. B가 11개인 위와 같은 경우 B를 9를 줘야 최대값이 나온다. 2. 이런 경우 자리수에 따른 가중치를 계산해야 한다. 1위 자리에 나온 수라면 +1의 가중치, 10의 자리라면 +10, ... 와 같은 방식이다. 예를들어 '예제 입력 1'에 나온 각 문자는 다음과 같이 가중치를 구할 수 있다. 그럼 가중치가 높은 순서대로 더 높은 수를 주면 된다(그리디). 따라서 B=9, A=8, C=7이 된다. 3. 만약 A~J가 아니라, A~I 까지 였다면 9~1을 주면 되니까.. 2021. 12. 18.
백준 3011 자바 - 이름 지어주기 (BOJ 3011 JAVA) 문제 : boj3011 1. A에서 B 구간의 최대가 10^9이므로, 우선 모든 경우를 봐서는 통과할 수 없음을 알 수 있다. 그럼 뭔가 정답 구간을 정할 수 있는 방법이 있다는 얘기이다. 이 문제의 경우, 어떠한 X 지점에 대해 모든 N지점 중 거리의 차가 최소인 지점을 최대한 멀리 두려고 한다(min{|X-Pi|, i ∈ [1,N]}). 즉, X는 모든 N개의 지점 P_i와 최대한 멀리 떨어지면 된다. 2. 입력이 4 10 46 56 70 10 70 인 경우를 생각해보자. 어떻게 해야 N개의 지점에서 가장 멀리 떨어진 X 지점을 모두 보지 않고 찾을 수 있을까? 최선의 선택은 각 지점들의 중간지점들을 보면, 그 중 가장 양쪽의 차이가 큰 지점을 고르면 될 것임을 생각해볼 수 있다(그리디). 그리고 하.. 2021. 12. 17.
백준 12834 자바 - 주간 미팅 (BOJ 12834 JAVA) 문제 : boj12834 문제의 입력 최대값 제한에 자비심이 넘치는 문제이다. 사실상 Floyd-Warshall만 딱 못쓰게 제한 걸고(V 2021. 12. 16.
백준 14911 자바 - 궁합 쌍 찾기 (BOJ 14911 JAVA) 문제 : boj14911 1. 주어지는 수의 개수가 주어지지 않으므로 입력받기 전에 총 배열의 크기를 알 수 없다. 미리 최대 개수 배열을 만들어 입력받은 후 처리하거나, 자바의 split 합수를 사용해 처리하면 된다. 2. 최대 개수가 10개밖에 안되므로 모든 경우의 수를 보면 된다. 다만 주의점은 사전 순으로 출력해야 한다는 부분인데, 이를 위해 정렬 후 모든 경우를 보면 된다. 또한 문제에 명시적으로 나타나진 않았으나, '사전 순으로 앞서는 기준은 a < c이거나, a == c 이면서, b < d 인 것' 에 따라 a==c이면서 b==d인 경우는 정의되지 않은 것을 알 수 있다. 따라서 서로 다른 쌍이라 할지라도, 동일한 출력값은 출력하면 안된다. 예를들어 입력이 1 1 1 1 1 2 와 같을 경우.. 2021. 12. 15.
백준 23716 자바 - Transform the String (BOJ 23716 JAVA) 문제 : boj23716 로직 자체는 별게 없다. S의 모든 문자열에 대해 각각 F의 각 문자열을 순회하며 가장 차이가 작은 문자를 고르면 된다. O(|S||F|) 다만 자바 한정으로 난이도가 급상승하는데, String으로 받는 순간 메모리 초과가 된다 ㅋㅋㅋㅋ (String은 char 배열형태이고, char은 2byte가 필요하다. byte 자료형은 1byte이다. -128~127까지 표현 가능하지만 어쨌든 소문자 표현은 가능하다.) C++이나 파이썬의 겨우엔 그냥 받아진다. 자바는 그래서 어떻게 해야 하냐면, character 배열인 String을 쓰면 안되고 모든 문자를 byte단위로 처리해야 한다. 따라서 byte 단위로 한 문자씩 입력받아 처리해야 한다. 아마 차후 자바의 경우 추가 메모리가 주.. 2021. 12. 14.
백준 9327 자바 - 용량 확보 (BOJ 9327 JAVA) 문제 : boj9327 음주코딩이 더 코딩이 잘된다는게 사실인것같다. 평소엔 시간 꽤나 걸리던 골1과 플5 문제가 둘다 한방에 해결됬다. 뭐지.. 이상하다. 아무래도 이것저것 복잡도 계산 해볼 정신머리가 없어서 무지성으로 짜보다 보니 오히려 빨리 해결하는 것 같다 ㅋㅋㅋ 결국 입력으로 주어진 n개의 용량x2에 대해 존재 가능한 모든 합의 경우의 수 중, 확보하려는 용량 e보다 같거나 큰 것 중 가장 가까운걸 출력하면 된다. 예를들어 n개가 400 600 700 일 경우 존재 가능한 모든 합의 경우의 수는 다음과 같다. 400 1000 1100 600 1300 700 이걸 정렬하면 400 600 700 1000 1100 1300 이 되고, 이 중 만약 e가 1050이라면 1050보다 같거나 큰 수중 가장 .. 2021. 12. 13.
백준 9213 자바 - 꽤 좋은 수 (BOJ 9213 JAVA) 문제 : boj9213 골드1 치곤 좀 쉬웠으나, 확실히 아이디어를 생각하긴 어려울수도 있을 것 같다. 우선 약수의 합을 구해보자. 소수판정 때 쓰던 에라토스테네스의 체를 쓰던 방식을 응용해서 소수를 구하는 것이 아니라, 약수를 구해 더해주면 각 수의 약수 의 합을 구할 수 있다. (코드 initBadness() 참고) 약수의 합을 구하는 것이므로, 에라토스테네스의 체의 최적화 방식인 sqrt(N) 까지가 아니라, N/2 까지 봐야 한다ㅇ 그럼 이후 [start, stop] 구간에 대해 미리 구해둔 약수의 합을 참고하여 i-arr[i]의 절대값이 badness 이하라면 카운팅하면 된다. 여기서 offline query + mo's algorithm까지 사용한다면 더 효율적으로 가능하겠으나 위의 방식으로 .. 2021. 12. 13.

티스토리툴바