0과 1의 쉼터

문제https://www.acmicpc.net/problem/3991 풀이문제의 규칙에 따라 구슬들을 없애면서 최대 점수를 구하는 문제다.최대 점수를 얻기 위해서는 종류가 C개인 구슬들을 종류 별 로 한 턴에 전부 없애면 된다.그러기 위해서는 구슬을 아래에서 위로, 왼쪽에서 오른쪽으로 계단을 쌓듯 구슬을 배치하면 된다. // Solve int idx = 0; for (int j = 0; j = 0; --i) { if (color[idx] 이제 오른쪽 위부터 구슬을 제거하면 남아있는 구슬들의 위치가 바뀌지 않으면서도 한 턴에 한 종류의 구슬을 모두 제거할 수 있다. 풀이 시간≤ 13m소스코드https://github.com/rogi-rogi/..

문제https://www.acmicpc.net/problem/2121 풀이N개의 점에 대해 x, y 축에 평행하는 직사각형의 수를 찾는 문제다.좌표를 한 쌍으로 묶어 집합에 넣어주고, Set set = new HashSet(); for (int i = 0; i 문제의 조건에 부합하는 좌표와 일치하는지 비교하는 방식으로 풀이했다. long cnt = 0; for (Point p : set) { if (set.contains(new Point(p.x + A, p.y)) && set.contains(new Point(p.x, p.y + B)) && set.contains(n..

문제https://www.acmicpc.net/problem/11663 풀이N개의 점으로 이루어진 선분에서 M개의 부분 선분 범위에 해당하는 점의 수를 세는 문제다.부분 선분의 범위를 각각 하한선과 상한선으로 원래 선분에서 이분 탐색을하면 된다. // Solve Arrays.sort(A); while (M-- > 0) { input = br.readLine().split(" "); sb.append(upperBound(Integer.parseInt(input[1])) - lowerBound(Integer.parseInt(input[0]))).append("\\n"); }풀이시간≤ 10m소스코드https://githu..

문제https://www.acmicpc.net/problem/27376 풀이구현 시뮬레이션에 시간도 계산해야 하는 문제라 난이도에 비해 까다로웠다.0에서 N까지 1씩 이동해야 하며, k개의 신호등이 초록불일 때만 이동하는 문제다.신호등의 위치가 순서대로 주어지는 보장이 없으니 입력받은 신호등 정보를 좌표 기준으로 오름차순 정렬하자. List list = new ArrayList(); for (int i = 0; i a[0]));정렬된 신호등까지는 1씩 이동한다. 마지막 위치에서 신호등 위치까지의 거리를 이용해 한 번에 계산하자. long time = 0, lastPos = 0; for (int[] info : list) { final..

문제https://www.acmicpc.net/problem/10844 풀이정수 N이 주어졌을 때, 길이가 N인 수 중 문제에 주어진 ‘계단 수’가 몇 개 인지 알아내는 문제다.우선 N이 1일 때 존재하는 계단 수는 1 ~ 9이다. int[][] dp = new int[N + 1][11]; for (int j = 1; j N이 2일 때는 이전 계단 수에서 1을 더하거나 뺀 값들이 새로운 계단 수가 된다.따라서 점화식을 다음과 같이 정의할 수 있다.dp[i][j] : 길이가 i이면서, 마지막 숫자가 j로 끝나는 계단 수dp[i][0]은 dp[i - 1][1]에서 1을 뺀 결과이고, dp[i][9]는 dp[i - 1][8]에서 1을 더한 값이다. for (int i = ..

문제https://www.acmicpc.net/problem/15658 풀이배열 A에 대해 주어진 연산자를 활용해 만들어지는 모든 식의 결과 중 최대/최소값을 구하는 문제다.중간값과, 다음에 계산할 요소의 인덱스를 넘겨주는 방식으로 풀이했다.만약 인덱스가 A의 길이와 같다면 더 이상 연산할 요소가 없기 때문에 연산을 중단하고 결과를 갱신했다. private static void bt(int temp, int nextIdx) { if (nextIdx == A.length) { max = Math.max(max, temp); min = Math.min(min, temp); return; }아직 연산할 요소가 남아있는 경..

문제https://www.acmicpc.net/problem/23827 풀이주어진 수열에 대해 1 ≤ i 수가 너무 커질 수 있으니 1e9 + 7로 나눈 나머지를 출력해야 한다.문제를 만족하는 정수쌍 곱의 합은 i와 i + 1 ~ j의 합의 곱과 같다.최대 길이가 50만인 수열에 대해 누적합을 미리 구해 // Solve final int MOD = (int) (1e9 + 7); long[] prefixSum = new long[N]; prefixSum[0] = A[0]; for (int i = 1; i 모든 i에 대한 A[i] * ( prefixSum[N] - prefixSum[i] )을 구하면 된다. long res = 0; ..

문제https://www.acmicpc.net/problem/32335 풀이주어진 문자열 S의 각 자릿수를 회전시켜 가장 작은 수를 만드는 문제다.총 M번 회전 시켜야 하며 수는 증가하는 방향으로 회전해야 한다.맨 앞자리부터 시작해서 0으로 만들 수 있을 만큼 M이 크다면 돌려주고, 아니면 다음 수로 넘어가면 된다. // Solve for (int i = 0; i '0') { final int num = S[i] - '0'; if (num + M >= 10) { S[i] = '0'; M -= (10 - num); } ..

문제https://www.acmicpc.net/problem/1639풀이주어진 문자열 S에 대해 2N자리의 부분 문자열의 각 자리를 더했을 때 왼쪽과 오른쪽 N자리의 합이 동일한 부분 문자열의 최대 길이를 구하는 문제다.우선 S의 길이에 따라 가능한 최대 크기를 정해주자.홀수면 1을 빼고, 짝수면 원래 크기 그대로 최대 크기가 될 수 있다. // Solve int GAP = nums.length % 2 == 0 ? nums.length : nums.length - 1;길이가 홀수인 정답은 없으므로 GAP이 0이 될 때 까지 2씩 감소시키며 문제의 조건을 만족시키는 부분 문자열을 찾으면 된다. while (GAP > 0) { for (int i = ..

문제https://www.acmicpc.net/problem/1388 풀이주어진 보드에서 ‘|’ 또는 ‘-’ 모양의 타일을 각각 세로와 가로로 전부 연결해서 만들어지는 판자들이 몇개 인지 구하는 문제다.판자가 아닌 타일들을 방문하면서 규칙에 따라 하나의 판자로 만들어주는 횟수를 세면 된다. // Solve int cnt = 0; for (int i = 0; i 현재 타일의 종류에 따라 가로 또는 세로로 연결된 동일한 종류의 타일들을 모두 방문해주자.만약 다른 종류의 타일이 나온다면 더 이상 연결할 수 없으므로 탐색을 중단해야 한다. private static void connect(int x, int y, char type) { if (type ==..