PS/AtCoder17 [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. [ABC252] A - ASCII code (AtCoder Beginner Contest 252 in Java) 문제 : abc252_a 아스키코드가 int로 주어지면 이걸 문자로 변경해서 출력해주면 된다. 따라서 단순히 입력된 int를 char로 캐스팅만 해주면 된다. 코드 : github ... private void solution() throws Exception { System.out.println((char)nextInt()); } ... 2022. 5. 22. [ABC251] C - Poem Online Judge (AtCoder Beginner Contest 251 in Java) 문제 : abc251_c 만약 공통된 String 부분이 없다고 생각해보자. 그럼 단순히 입력 중 최대 T값이 인덱스를 출력해주면 될 것이다. 다만 이 문제에서는 S를 기준으로 중복된 값이 들어왔다면 해당 값은 무시해줘야 한다. 동일한 String이 들어왔는지 확인하는 가장 간단한 자료구조는 HashSet을 사용하는 것이다. 따라서 HashSet으로 이미 들어온 값이라면 무시하고, 그렇지 않다면 HashSet에 등록하고 최대값인지 체크하면 된다. 코드 : github ... private void solution() throws Exception { int n = nextInt(); HashSet hs = new HashSet(); int max = 0; int maxIdx = 0; for (int i .. 2022. 5. 15. [ABC251] B - At Most 3 (Judge ver.) (AtCoder Beginner Contest 251 in Java) 문제 : abc251_b 1~3개의 합이 W이하인지 확인하는 문제이다. 최소 1개, 최대 3개를 모두 골라보면 된다. 따라서 모든 경우를 확인하는데 O(N^3)이 필요하며, N이 최대 300개이므로 시간은 널널하다. 중간에 합이 W보다 커지는 경우 해당 경우를 확인하지 않는 백트래킹 개념도 더하면 더 효율적으로 짤 수 있다. 주의점은 모든 경우 중, W이하를 만족하는 모든 경우를 구하는게 아니라 그러한 합계를 구해야 한다. 따라서 HashSet 등을 통해 중복된 값은 카운팅 하지 않도록 별도로 처리가 필요하다. 코드 : github ... int n, w, ans=0; int[] arr; boolean[] v; HashSet hs = new HashSet(); private void proc(int id.. 2022. 5. 15. [ABC251] A - Six Characters (AtCoder Beginner Contest 251 in Java) 문제 : abc251_a S를 6/|S| 번 반복출력해주면 된다. 코드 : github ... private void solution() throws Exception { String s = nextLine(); String ans = ""; for (int i = 0; i < 6/s.length(); i++) { ans += s; } System.out.println(ans); } ... 2022. 5. 15. 이전 1 2 다음
