PS/AtCoder21 [ABC301] D - Bitmask (AtCoder Beginner Contest 301 in Java) 목차 문제 : ABC301 - D 필요 알고리즘 문자열, 수학 이진수에 대한 수학적인 사고가 좀 필요한 문제이다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 1. 우선 '?'를 전부 '0'으로 바꿔본다. (만들 수 있는 최소값) 그게 n과 동일하다면 n이 답이고, n보다 크다면 애초에 불가능한 경우이므로 -1을 출력하고 끝낸다. 2. 다음으로 '?'를 전부 '1'로 바꿔본다. (만들 수 있는 최대값) 그게 n 이하라면 그.. 2023. 5. 13. [ABC301] C - AtCoder Cards (AtCoder Beginner Contest 301 in Java) 목차 문제 : ABC301 - C 필요 알고리즘 그리디 그리디라고 하기 좀 애매하긴한데, 아무튼 바꿀 수 있으면 대충 바꾸는 로직으로 풀 수 있으므로 일단 그리디라 적었음. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 cnt 배열에 'a'부터 'z' 까지 S에 나온 문자만큼 +1, T에 나온 문자만큼 -1을 해주며 세줬다. 예를들어 S가 "ABC", T가 "BCD" 라면 cnt[0] = 1, cnt[1] = 0, cnt[2.. 2023. 5. 13. [ABC301] B - Fill the Gaps (AtCoder Beginner Contest 301 in Java) 목차 문제 : ABC301 - B 필요 알고리즘 구현 문제에서 제시된 방법대로 구현하면 된다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 직전 숫자와의 차이가 1 이상이라면 사이값을 채워넣어주면 된다. List res = new ArrayList(); res.add(arr[0]); for (int i = 1; i < n; i++) { if (Math.abs(arr[i-1] - arr[i]) arr[i]; j--) res... 2023. 5. 13. [ABC301] A - Overall Winner (AtCoder Beginner Contest 301 in Java) 목차 문제 : abc301 - A 필요 알고리즘 구현, 문자열 문제에서 제시된 대로 구현하는 문제이다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 문자열의 각 문자를 읽는방법을 안다면 풀 수 있다. T와 A가 나온 갯수를 세서 더 많은 쪽의 문자를 출력해주면 된다. 다만 갯수가 동일하다면 최대치에 더 먼저 도달한 문자를 출력해줘야 한다. 이 부분은 코드에서 'c' 변수로 처리했다. 코드 : github import jav.. 2023. 5. 13. [ABC259] D - Circumferences (AtCoder Beginner Contest 259 in Java) 문제 : abc259_d 내 경우엔 그래프로 변경해서 풀었다. 우선 ArrayList의 idx를 기준으로 0번에 s, 1번에 t를 둔다. 이후 N개의 원을 입력받으면서 s와 t를 포함해서 모든 원의 쌍들에 대해 서로 인접해 있다면 양방향 간선을 연결한다(코드의 edgeChk, O(3000^2)). 단, s와 t의 경우엔 외곽선에 겹칠 경우에만 겹친다고 판단하고 간선을 연결한다(코드의 circumferenceChk). 예를들어 이하의 입력을 보자. 4 0 -2 3 3 0 0 2 2 0 2 2 3 1 -3 3 3 이에 대한 이미지와 각 idx는 다음과 같다. 그리고 간선정보는 다음과 같다. (예를들어 1행 4열의 v는 idx 1과 idx 4가 인접함을 뜻한다.) 그럼 이제 이 문제는 N+2개의 정점이 있는 .. 2022. 7. 11. [ABC259] C - XX to XXX (AtCoder Beginner Contest 259 in Java) 문제 : abc259_c 내 경우엔 String을 다음과 같이 압축시켜서 판단했다. abbaac => a1 b2 a2 c1 abbbbaaac => a1 b4 a3 c1 위와 같이 압축시킬 경우, 다음과 같이 판단할 수 있다. 1. 압축시킨 갯수가 다를 경우 No (예를들어 a1 b2 c2 vs a1 b2 였다면 3개와 2개로 비교해볼 것도 없이 No 이다.) 2. 압축시킨 부분에서 문자 부분이 서로 다른 경우 No (예를들어 a1 b1 c1 vs a1 d1 c1) 3. 압축시킨 각 부분에서 숫자가 S를 압축시킨쪽이 더 큰 경우 No (예를들어 a2 vs a1) 4. 압축시킨 각 부분에서 숫자가 서로 다른데, S가 1인 경우 No (예를들어 a1 vs a2) 5. 이외의 경우 Yes 코드 : github .. 2022. 7. 11. [ABC259] A - Growth Record (AtCoder Beginner Contest 259 in Java) 문제 : abc259_a 예를들어 N=4, T=10, D=3, X=3 인 경우를 그려보면 다음과 같다. 이 때, X부터는 변화가 없으므로 M이 X이상이라면 단순히 T가 답이 된다. 그 이하의 경우가 문제인데 그 이하의 경우엔 일정하게 줄어들게 되므로 T-(X-M)*D 가 될 것이다. 말로 설명하면 [X일때의 키(T)]-[X에서 몇 번 D만큼 내려가야하는지(X-M)]*[키의 변화수치(D)] 이다. 코드 : github ... private void solution() throws Exception { int n = nextInt(); int m = nextInt(); int x = nextInt(); int t = nextInt(); int d = nextInt(); if (m >= x) { System... 2022. 7. 11. [ABC252] E - Road Reduction (AtCoder Beginner Contest 252 in Java) 문제 : abc252_e 다익스트라 자료구조에 대해 이해를 하고있다면 쉽게 풀 수 있다. 문제에서 제시된 d2+d3+...+dN의 합을 최소화 한다는 말은 즉, 1부터 모든 정점으로의 최단거리를 가지는 N-1개의 edge를 남겨야 한다는 말과 동일하다. 1부터 모든 정점으로의 최단거리는 다익스트라를 돌리면 얻을 수 있고, 다익스트라의 결과는 모든 정점으로의 경로가 존재했다면 N-1개만 남게 된다. 그러므로, 단순히 정점 1부터 시작하는 다익스트라를 구현하고, 이 때 각 정점으로 마지막으로 들어왔던 간선(즉, 각 정점으로 들어온 1부터 최단거리에 해당하는 간선)을 저장해둔 후 그걸 출력해주면 된다. 이 때 'in arbitrary order' 라고 했으므로(랜덤 순서를 뜻한다) 아무 순서로든 출력만 해주면.. 2022. 5. 22. [ABC252] C - Slot Strategy (AtCoder Beginner Contest 252 in Java) 문제 : abc252_c arr[a][b]는 a라는 수(016(=6+10)으로 눌러야 하므로 16초가 필요하다. arr[1]의 경우엔 0->1->7이므로 7초, arr[2]는 0->2->9이므로 9초... 이런식이다. 이 중 가장 작은 것은 arr[8]로 0->2->6으로 6초가 된다. 이런식으로 arr[a][b]를 구해둘 시 arr[0]~arr[9] 각각의 초를 구하고, 그 중 가장 작은 초를 출력해주면 된다. 코드 : github ... private int getTime(int[] cnt) { int max = 0; for (int i = 0; i < 10; i++) { int calc = i+(cnt[i]-1)*10; max = Math.max(calc, max); } return max; } p.. 2022. 5. 22. [ABC252] B - Takahashi's Failure (AtCoder Beginner Contest 252 in Java) 문제 : abc252_b N개의 입력값 중 가장 큰 수를 제외한 데이터는 의미가 없다. 결국, N개의 입력값 중 가장 큰 수의 인덱스들이 K개의 입력값 중에 포함된다면 Yes, 아니라면 No를 출력해주면 되는 문제이다. 따라서 내 경우엔 N개를 입력받으면서 max 값을 찾는다. 이 때 새로운 max값이 나타난다면 HashSet을 초기화하고, max값과 동일한값이 나타날 시 HashSet에 추가하는 식으로 진행했다. 이후 K개를 입력받으면서 HashSet에 있는지만 판단해줬다. 코드 : github ... private void solution() throws Exception { int n = nextInt(); int k = nextInt(); HashSet hs = new HashSet(); int .. 2022. 5. 22. 이전 1 2 3 다음
