중복 제거 => TreeSet 사용2가지 기준의 정렬import java.io.BufferedReader;import java.io.InputStreamReader;import java.util.*;public class Main { public void solution() throws Exception{ BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int n = Integer.parseInt(br.readLine()); StringBuilder sb = new StringBuilder(); // TreeSet을 사용하여 중복 제거 + 정렬 Set s..
https://www.acmicpc.net/problem/2193DP 문제dp[i] = dp[i-1] + dp[i-2]int 형의 범위를 벗어나기 때문에 long 타입의 배열을 사용해야 함import java.io.BufferedReader;import java.io.InputStreamReader;public class Main { public void solution() throws Exception{ BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int n = Integer.parseInt(br.readLine()); if(n == 1){ System...
https://www.acmicpc.net/problem/11726dp[i] = dp[i-1] + dp[i-2]import java.io.BufferedReader;import java.io.InputStreamReader;public class Main { public void solution() throws Exception{ BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int n = Integer.parseInt(br.readLine()); if(n == 1){ System.out.print(1); return; } ..
https://www.acmicpc.net/problem/11660[(0,0) ~ (x2,y2) 합] - [(0,0) ~ (x1 -1, y2) 합] - [(0,0) ~ (x2, y1 -1) 합] + [(0,0) ~ (x1-1,y1-1) 합]각 좌표까지의 누적합을 먼저 구해두고 이를 사용하여 M쌍의 좌표들에 대한 값을 구함import java.io.BufferedReader;import java.io.InputStreamReader;import java.util.StringTokenizer;public class Main { public void solution() throws Exception{ BufferedReader br = new BufferedReader(new InputSt..
https://www.acmicpc.net/problem/1149DP 문제이기 때문에 어떤 값을 저장하고, 다음 회차에서 사용할 수 있게 할 지를 고민해야 한다!양 옆의 집 색과 다른 색을 칠해야 함비용이 최소여야 함N번 집을 칠할 때 고려해야 하는 것은 직전 집의 색이고, 또한 해당 집을 칠할 때 직전 색을 쓰지 않으면서 비용이 최솟값이 되어야 함현재 칠할 색이 A라고 했을 때, 고려해야 할 것은 직전 색 B, C를 칠한 경우의 수 중 비용이 최소인 것임따라서 각 세가지 색을 칠할 경우에 나올 수 있는 N번 집까지의 비용의 합 경우를 따져야 함 비용을 위한 배열을 N x 3 형태로 만들고, n번 집의 비용을 입력받은 후 직전 집들의 비용과 합친 것을 저장마지막 n-1 행에는 모든 집들의 비용 합이 있고..
https://www.acmicpc.net/problem/2579Dynamic Programming으로 풀 때는, 어떤 정보를 자료구조(혹은 배열)에 저장해야 다음 단계에서 적절하게 사용가능할 지를 생각해야 한다.이번 문제에서는, 한 계단씩 이어서 세 번을 오르는 것이 불가하므로 직전에 연속으로 계단 하나씩 오른 횟수를 알아야 하고, 또한 그때까지의 점수의 합도 저장해야 한다.계단은 한계단씩 최대 연속 2회까지 가능하므로 이를 고려하여 배열의 구조를 설계한다.초기 두 칸을 제외하고, 세 칸 연속 밟을 수 없으므로 직전에 한칸을 0회연속, 1회연속 밟은 것을 고려하기 위해 n행 2열 형태로 배열을 구성한 후, 두칸을 밟는 경우와 한칸을 밟는 경우를 계산하여 저장하였다.import java.io.Buffer..
https://www.acmicpc.net/problem/2292import java.io.BufferedReader;import java.io.InputStreamReader;public class Main { public void solution() throws Exception{ BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int n = Integer.parseInt(br.readLine())-1; if (n==0){ System.out.print(1); return; } int c = 0; w..
https://www.acmicpc.net/problem/2630색종이를 자르기 위해 시작점과 길이를 큐or스택에 저장저장해둔 색종이 정보를 빼서, 모두 같은 색이면 뺀 후 저장하지 않음. 색종이 개수 추가모두 같은 색이 아니라면 또 반으로 잘라서 저장 / 혹은 길이가 1이면 더 이상 자를 수 없기에 멈춤색을 판단하기 위해서는 해당 종이에 적힌 수의 합을 더해서 넓이와 값을 비교한다.0이거나 넓이와 같아야 모두 같은색이다.import java.io.BufferedReader;import java.io.InputStreamReader;import java.util.ArrayDeque;import java.util.Arrays;import java.util.Deque;public class Main { ..
https://www.acmicpc.net/problem/9461P(N)은 P(N-1)와 P(N-5)의 합과 같음즉 N이 주어졌을 때, P(1) ... P(N)까지 합을 더해가며 구하면 된다단,p[1]=p[2]=p[3]=1;p[4]=p[5]=2;p[6]=3;으로 규칙적으로 값이 더해지기 이전의 초기 설정들은 미리 값을 넣어주어야 한다.import java.io.BufferedReader;import java.io.InputStreamReader;public class Main { public void solution() throws Exception{ BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); ..
https://www.acmicpc.net/problem/11047값이 큰 동전이 가장 마지막에 입력되기 때문에, LIFO로 값을 꺼내와서 개수를 카운트해야 한다.따라서 Stack 형태로 동전 값들을 저장하면 된다.import java.io.BufferedReader;import java.io.InputStreamReader;import java.util.Stack;import java.util.StringTokenizer;public class Main { public void solution() throws Exception{ BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringT..
