![]()
https://www.acmicpc.net/problem/2096 설명N은 1 이상 10만 이하로, 한 줄에는 3칸이 있고 각 칸에는 최대 9까지 올 수 있으므로, 최악의 경우의 합을 더해도 9 * 10만 = 90만으로 int의 최댓값보다 작다. 또한 메모리가 4MB인데, 4byte(int) * 3칸 * 10만 줄 = 1.2MB로, 입력받는 배열에 최댓값, 최솟값 + 기타 연산하면서 생기는 객체들까지 고려하면 메모리 초과가 날 것 같았다. 그래서 입력 배열은 따로 만들지 않고 최댓값 배열과 최솟값 배열만 만들되, 각각 2 * 3 배열을 만들어서 값을 재사용하기로 했다. 우선 N과 최댓값 배열 maxArr, 최솟값 배열 minArr을 선언해준다. 그리고 각 배열을 2*3으로 초기화해준다. i / j0..
https://www.acmicpc.net/problem/11048 설명전형적인 DP 문제이다. 문제에서는 (r+1, c), (r, c+1), (r+1, c+1)로 이동할 수 있다는 부분 때문에 현재 위치를 기준으로 다음 위치의 값을 어떻게 넣어줄지 생각하게 되는데, DP는 역으로 현재 위치의 값이 과거의 어느 위치로부터 영향받았는지로 생각하면 조금 더 수월하게 풀린다. 물론 그래도 DP는 너무 어렵다.,... 문제의 답이 N, M에 도착할 때 가장 많은 사탕을 가지고 있어야 하는 경우이고, 이동은 오른쪽, 아래, 오른쪽 아래 대각선 3방향으로 밖에 이동하지 못한다는 조건으로 생각해 보자. 두 번째 조건을 반대로 생각해보면, 현재 위치에 있으려면 그전에는 왼쪽, 위, 왼쪽 위 대각선 중 하나에 있어야..
https://www.acmicpc.net/problem/1520 설명처음에는 BFS로 풀었다. 근데 BFS로 노드를 지나가면서 방문 체크를 해두는데, 이미 방문한 노드에 대해서는 이후 다른 경로에서는 거치지 않기 때문에 경로가 딱 1개만 나왔다. 그렇다고 지나간 경로를 체크 안 하면 무한 루프에 빠져서 BFS는 버렸다. 그 다음에는 DFS로 풀었다. 답은 나왔는데, 시간 초과가 떴다. 그래서 곰곰이 생각하다가 DP로 풀었더니 풀렸다. 탑다운 방식으로 풀었다.범위를 벗어나는 좌표에서는 0을 리턴하고, 이미 계산한 좌표에서는 그대로 계산 값을 리턴하고, 아직 계산하지 않는 좌표에 대해서는 현재 좌표의 상하좌우의 높이를 비교해서 현재 높이보다 큰 인접 좌표에 대해서 재귀로 dp를 호출했다. stat..
https://www.acmicpc.net/problem/1202 맨 아래에 전체 코드 있다. 설명 처음에 배낭문제 인줄 알았는데 가방이 여러 개라 어떻게 풀지 고민하다가 가방에 1개의 보석만 담을 수 있어서 아닌 것 같았다(?) 일단 보석을 객체로 만들고, 가방 최대 무게 배열을 오름차순으로 정렬보석 리스트를 (1) 무게 오름차순, (2) 가격 내림차순 정렬 매 가방마다 보석 리스트 돌며 최대 무게 이하인 보석만 우선순위 큐에 넣기 (우선순위 큐는 2번과 같이 정렬됨)하나 poll 해와서 가격을 총 더하고, 더한 보석은 보석리스트에서 제거 출력 인줄 알았는데 시간 초과가 났다. 아무래도 보석과 가방 개수가 최대 30만개에, 이중 반복문이면 900억이어서.. 그래서 풀이 봤다! 근데 풀이 설명..
https://www.acmicpc.net/problem/11655 import java.util.Scanner;public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); String str = sc.nextLine(); char[] chars = str.toCharArray(); for (int i = 0; i 'Z') || (Character.isLowerCase(ch) && n > 'z')) { n -= 26; } chars[i] = (char) n; ..
https://www.acmicpc.net/problem/10825 import java.io.*;import java.util.*;public class Main { static int N; static List students = new ArrayList(); static StringBuilder sb = new StringBuilder(); static int stoi(String s) { return Integer.parseInt(s); } public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStrea..
https://www.acmicpc.net/problem/1076 import java.io.*;import java.util.*;public class Main { static Map map = Map.of( "black", "0", "brown", "1", "red", "2", "orange", "3", "yellow", "4", "green", "5", "blue", "6", "violet", "7", "grey", "8", "white", "9" ); static long stol(String s) { return Long.parseLong(s..
https://www.acmicpc.net/problem/1977 import java.io.*;public class Main { static int N, M, total; static int min = Integer.MAX_VALUE; static int stoi(String s) { return Integer.parseInt(s); } public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); M = stoi(br.readLine()); N ..
https://www.acmicpc.net/problem/1145 import java.io.*;import java.util.*;public class Main { static int N; static int[] arr = new int[5]; static int stoi(String s) { return Integer.parseInt(s); } public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new String..
