본문 바로가기

백준757

백준 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.
백준 11609 자바 - Class Time (BOJ 11609 JAVA) 문제 : boj11609 order by last asc, first asc의 형태로 정렬하면 된다. 문자열을 입력 받아 띄어쓰기를 기준으로 나눌 줄 알고, 정렬하는 방법을 안다면 쉽게 풀 수 있다. 코드 : github import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.Arrays; import java.util.StringTokenizer; class Name implements Comparable { String first, last; public Name(String name) { StringTokenizer st = new StringTokenizer(name); first = st.nextToken.. 2022. 1. 29.
백준 15922 자바 - 아우으 우아으이야!! (BOJ 15922 JAVA) 문제 : boj15922 결국 겹치는 구간은 무시하고, 모두 그려봤을 때 실제 포함되는 구간만을 구하면 된다. 이에 따라 예제 입력 1은 다음과 같이 생각해볼 수 있다. 그렇다고 배열같은거에 기입하자니 20억개나 표현이 가능해야하고, 당연히 이건 단순 순회만으로도 시간초과가 나게 된다. 따라서 내 경우엔 우선 각 x값을 기준으로 정렬한 후 현재 측정중인 구간의 시작 x와 끝점 y를 따로 기록해뒀다(코드에서 s와 e). 로직은 다음과 같다. A. x값을 기준으로 오름차순으로 정렬된 데이터를 차례대로 확인한다. 첫 s와 e는 즉 가장 x가 낮은 데이터 중 하나의 값과 동일해진다. B. 이후 각 (x,y)를 순회하면서 x가 e 이하라면 이전까지 보고 있던 (x,y)와 같은 구간으로 칠 수 있으므로 e만 조정한.. 2022. 1. 28.

티스토리툴바