본문 바로가기

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.