잡동사니_로드

예를 들어, 10-20+30-40+50이란 식에 괄호를 쳐 최솟값을 만들기 위해서는 10-(20+30)-(40+50) 로 치면 된다.-를 기준으로 문자열을 나눠 (10, 20+30, 40+50 )초기 값 (10)은 더하고, 이후 더하기 식의 결과는 (50, 90) 은 초기 값에서 빼 답을 구할 수 있다. import java.util.*;import java.io.*;public class Main { static int answer; public static void main (String [] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)..

합이 최대가 하기 위해서는 양수는 양수끼리, 음수/0은 음수/0끼리 곱하고 1은 더해야 한다.양수는 큰 수 끼리, 음수는 절댓값이 큰 수 끼리 곱해야 보다 큰 수를 만들 수 있으므로 우선순위 큐를 통해 답을 도출할 수 있다. import java.util.*;import java.io.*;public class Main { static int n, answer; static PriorityQueue plusPq = new PriorityQueue(Collections.reverseOrder()); static PriorityQueue zeroAndMinusPq = new PriorityQueue(); public static void main (String [] arg..

우선순위 큐를 이용해서 해결할 수 있다! n = 1 인 경우에는 이미 정렬이 완료된 카드 묶음 1개만 있으므로 답은 0이다 40 20 10 -> 10, 20 비교 (10 + 20 = 30), 30 다시 offer (answer += 30)40 30 -> 30, 40 비교 (30 + 40 = 70), 70 offer (answer += 70)70 -> 모든 카드 묶음 비교해 하나의 카드 묶음만 남았으므로 종료 import java.util.*;import java.io.*;public class Main { static int n, answer; static PriorityQueue pq = new PriorityQueue(); public static void main (..

크기가 3 * 3인 이차원 배열 생성해 수를 저장하고, 일차원 배열에 오름차순 정렬해 넣으면1 2 2 3 3 4 6 6 9 가 저장되고, B[7] = 6이므로 (index는 이차원/일차원 모두 1부터 시작) 위 예제에서의 답은 6이다. 정렬 후 배열 B 안 K번째 수가 x라면, x보다 작거나 같은 수가 "최소" k개 있다는 것으로 해석할 수 있다. - ex1) 위 입력에서 k=8이었다면 B[8] = 6, 6 이하 수가 총 8개 존재한다. (k와 같다) (1, 2, 2, 3, 3, 4, 6, 6) - ex2) 위 입력에서 k=7이었다면 B[7] = 6, 6 이하 수가 총 8개 존재한다. (k보다 크다) (2, 3, 6처럼 같은 수가 여러 개 있을 수..

기본적인 BFS 문제다 import java.util.*;import java.io.*;public class Main { static int n, m; static int answer = Integer.MAX_VALUE; static int [][] board; static int [] dn = {-1, 0, 1, 0}; // 12, 3, 6, 9 static int [] dm = {0, 1, 0, -1}; // 12, 3, 6, 9 static Deque queue = new ArrayDeque(); static boolean [][] isVisited; public static void main (String [] args) throws Except..

1이 적힌 칸을 모두 색종이로 덮을 수 있는 지 판단해야 한다. import java.util.*;import java.io.*;public class Main { static int answer = Integer.MAX_VALUE; static int [][] board = new int[10][10]; static int [] paperCount = {0, 5, 5, 5, 5, 5}; // 각 paper 할당된 종이 수 ex) paperCount[5] answer) return; if (board[x][y] == 1) { for (int paperIndex=5;paperIndex>=1;paperIndex--) { ..

체스에서 퀸은 한 번에 가로, 세로, 대각선 칸으로 이동하는 칸 수 제한없이 이동할 수 있다. 즉 체스판의 가로 한 줄당 하나의 말만 올 수 있으므로 가로줄에 있는 말의 위치를 저장하는 queenPosition 배열을 통해 가로/세로 판별이 가능하다. 대각선에 있는지 파악하기 위해서는 기울기의 정의인 체스에서 퀸은 한 번에 가로, 세로, 대각선 칸으로 이동하는 칸 수 제한없이 이동할 수 있다. 즉 체스판의 가로 한 줄당 하나의 말만 올 수 있으므로 가로줄에 있는 말의 위치를 저장하는 queenPosition 배열을 통해 가로/세로 판별이 가능하다. 대각선에 있는지 파악하기 위해서 인덱스의 차이 (가로줄 차이)와 값의 차이 (세로줄 차이) 를 계산해, 둘이 같다면 같은 대각선에 있다 판단할 수 있다. ..

import java.util.*;import java.io.*;public class Main { static int n, m; static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out)); static boolean [] isVisited; static int [] answer; public static void main (String [] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); Stri..

Inversion Count (배열 내 i arr[j]의 경우의 수) 의 수를 구하는 문제이다. 위 3 2 1 경우를 보면 (3 2) (3 1) (2 1) 에만 발생한다. Merge Sort 중 병합 과정에서 두 번째 dataset의 데이터가 첫 번째의 것보다 작아 tmp 배열에 정렬될 때, 첫 번째 dataset에 남아 있는 data의 수만큼 inversion 경우의 수를 만들 수 있으므로, 이 상황 때마다 answer에 더해주면 된다. - ex) 5 4 / 3 7 merge 시, 5 > 3이므로 3이 먼저 tmp 배열에 들어간다. inversion 경우의 수는 (5 3) (4 3)이 발생하므로 이 때 2를 더해주자 import java.util.*;import java.io.*;public ..

cf > cout는 C++ 에서 출력을 의미한다 위 cout 이 실행될 때에는 정렬 완료된 다음 loop에서 발생한다. 이를 위해 각 loop 당 왼쪽으로는 1번씩 이동하는 걸 이용할 수 있다. 정렬 전/후 index를 비교해서 왼쪽으로 움직인 정도의 최댓값 + 1을 출력하자 (+1은 정렬이 제대로 되었는지 확인 후 출력 위한 loop) - ex) 10 1 5 2 3 1 5 2 3 10 import java.util.*;import java.io.*;public class Main { static int n; static int answer = Integer.MIN_VALUE; static List list = new ArrayList(); ..