SH

https://www.acmicpc.net/problem/2512이분탐색 1. 모든 요청이 배정될 수 있는 경우에는 요청한 금액을 그대로 배정한다.sum 2. 모든 요청이 배정될 수 없는 경우에는 특정한 정수 상한액을 계산하여 그 이상인 예산요청에는 모두 상한액을 배정한다. 상한액 이하의 예산요청에 대해서는 요청한 금액을 그대로 배정한다. 이분 탐색한다. import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.StringTokenizer;class Main { public static void main(String[] args) throws IOException ..

https://www.acmicpc.net/problem/2688dp 문제 i번째 숫자에 어떤 num으로 도달했냐가 핵심이고, 0~i-1번째에 사용된 숫자는 유효하다면 기록할 필요가 없다. 수식dp[i][num] = ∑k=0num-1 dp[i-1][k] import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int TC = Int..

https://www.acmicpc.net/problem/2149 문자열/정렬 문제 문제를 대충 읽으면 낭패본다. 1. 문제 설명은 암호화에 관한 것이고, 출력은 복호화를 요구한다.2. 평문은 가로를 기준으로 구성하고, 암호문은 세로를 기준으로 구성해야 한다. import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.Arrays;import java.util.Comparator;class Main { static class E { int num; char alpha; char[] chars; E(int num, char alpha, char[] ch..

https://www.acmicpc.net/problem/2346 덱 문제 리스트 기반으로 점화식을 세워서 풀었다.덱보다 성능은 좋을 것 같고, 대신 문제 난이도는 어려워졌다. 다음 풍선 위치 구하기 풍선에 쓰인 수가 양수 :1. 다음 인덱스 = (현재 인덱스 + 쓰인 수 - 1) % 현재 리스트 사이즈(-1 하는 이유 : 리스트에서 idx번째 원소를 remove했으므로, idx가 기존의 idx+1번째 원소를 가리키는 것 상쇄) 풍선에 쓰인 수가 음수 :1. 다음 인덱스 = (현재 인덱스 + 쓰인 수) % 현재 리스트 사이즈(왼쪽으로 탐색하니 -1 하지 않는다.) 2. 1번 값이 음수라면, 다음 인덱스 = 현재 리스트 사이즈 + 다음 인덱스(파이썬처럼 -1, -2가 size - 1, size - 2..

https://www.acmicpc.net/problem/2811 구현 문제 일단 모든 우울 구간에서 2T 만큼 꽃을 준다.최대 우울 구간 리스트를 순회하며, 각각 3T 만큼 꽃을 줘보고 최대값인 경우를 도출한다. flower는 너무 길어서 rose로 썼다.import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.ArrayList;import java.util.List;import java.util.StringTokenizer;class Main { public static void main(String[] args) throws IOException { Buff..

https://www.acmicpc.net/problem/3107 문자열, 파싱 문제인데 생각보다 복잡했고 여러 방법이 있을 것 같다. 배운 점 String.split(regex, limit)에서,limit를 -1로 지정해야 끝의 연속된 빈 필드까지 원소로 포함시킨다.문제에서 가능한 입력 중, 다음과 같은 경우 차이가 일어난다. input:::split(":") => [] size0의 배열split(":", -1) => [,,] => size3의 빈 배열 이유는,split(regex) == split(regex, 0) 이며,limit=0일 때는 끝에서 부터 내용이 존재하지 않는 곳은 포함하지 않는 것이 기본 동작이다. input::::a:::a::::output: Arrays.toString(spl..

https://www.acmicpc.net/problem/2597 구현 문제 : 줄자를 세번 접었을 때, 길이 출력 import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.StringTokenizer;class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); double ans = Integer.parseInt(br.readLine()); double..

https://www.acmicpc.net/problem/2548 정렬했을 때, 모든 원소와 차이를 최소로 하는 숫자는 항상 중앙에 위치한다. 처음에 중앙 인덱스를 다음과 같이 표현했다.짝수 일 때 : (a.len / 2) - 1홀수 일 때 : a.len / 2 ac이후 다른 코드에서, 분기처리할 필요 없음을 알게 되었다.짝/홀수 일 때 : (a.len -1) / 2import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.Arrays;class Main { public static void main(String[] args) throws IOException { B..

https://www.acmicpc.net/problem/2713 구현 문제(매우 귀찮고 실수하기 쉬운 내용이 많은) 1. 파싱하기2. 5자리 이진수 코드 맵핑하기 [A-Z, 공백]3. 나선형 배열 채우기 파싱이 제일 어려웠다. 처음에 StringTokenizer을 쓰다가, 공백으로 구분하면 다음과 같은 케이스가 까다로움을 파악했다. 35 5 A A5 5 5 5 A 어느 경우던 토큰이 없어서 NPE거나, 제대로 못받는 등 처리가 어려웠다.이후 String.split() 에 limit를 지정할 수 있는 걸 찾아서 해결했다.import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;impo..

https://www.acmicpc.net/problem/2716 분류는 스택/트리인데, 직접 사용하지 않아도 해결 가능하다. [ [] ] , [ [] [] ] -> 최대 높이 = 2[ [] [ [] ] ] -> 최대 높이 = 3 즉, 어떤 덩굴(트리)의 높이는, [] 모양으로 둘러쌓인 횟수를 의미한다. 1. 매 순간 [가 등장하면 h++하고, ]가 등장하면 h--한다. 동시에, max h값을 갱신한다. 2. 문제의 정의에 따라, 덩굴은 매 순간 두 개로 나눠진다.=> 높이가 1 증가할 때마다, 현재 높이에 매달린 원숭이 수의 두 배 만큼 분기한다. 3. 문제의 정의에 따라, 덩굴 마다 매달린 원숭이의 수는 모두 같아야 한다.=> 높이에 따라 여러 트리 모양이 나올 수 있지만, 노드의 수는 차이가 있어..