6-6화이탱

https://www.acmicpc.net/problem/11650 11650번: 좌표 정렬하기 첫째 줄에 점의 개수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개의 줄에는 i번점의 위치 xi와 yi가 주어진다. (-100,000 ≤ xi, yi ≤ 100,000) 좌표는 항상 정수이고, 위치가 같은 두 점은 없다. www.acmicpc.net 객체를 생성하여 x.y값을 비교 정렬하면 된다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arrays; import java.util.Comparator; import java.util.St..

https://www.acmicpc.net/problem/10942 10942번: 팰린드롬? 총 M개의 줄에 걸쳐 홍준이의 질문에 대한 명우의 답을 입력으로 주어진 순서에 따라서 출력한다. 팰린드롬인 경우에는 1, 아닌 경우에는 0을 출력한다. www.acmicpc.net 배열로 간단하게 해결 가능한 문제였다. 배열을 하나 더 만든 후, 기존의 배열을 뒤집은 값을 넣고 두 배열을 비교하는 방법도 존재한다! import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main { static int[] arr; stat..

https://www.acmicpc.net/problem/15486 15486번: 퇴사 2 첫째 줄에 N (1 ≤ N ≤ 1,500,000)이 주어진다. 둘째 줄부터 N개의 줄에 Ti와 Pi가 공백으로 구분되어서 주어지며, 1일부터 N일까지 순서대로 주어진다. (1 ≤ Ti ≤ 50, 1 ≤ Pi ≤ 1,000) www.acmicpc.net dp문제로, 배열을 생성하여 n번쨰 날짜에 받을 수 있는 돈을 저장한다. 그리고 for문을 돌면서 가장 큰 값을 max로 넣고, 배열에 가장 큰 값을 넣는다. 이 문제의 핵심은 하루 걸리는 업무가 마지막날 존재한다면 해당 업무는 할 수 있는 것이기에, n+2까지 진행해야한다는 것이다.!! import java.io.BufferedReader; import java.i..

https://www.acmicpc.net/problem/14425 14425번: 문자열 집합 첫째 줄에 문자열의 개수 N과 M (1 ≤ N ≤ 10,000, 1 ≤ M ≤ 10,000)이 주어진다. 다음 N개의 줄에는 집합 S에 포함되어 있는 문자열들이 주어진다. 다음 M개의 줄에는 검사해야 하는 문자열들이 주어 www.acmicpc.net Set 을 사용해서 set에 존재하는 것이면 count++ 을 하였다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.HashSet; import java.util.Set; import java.util.StringT..

https://www.acmicpc.net/problem/2096 2096번: 내려가기 첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 숫자가 세 개씩 주어진다. 숫자는 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 중의 하나가 된다. www.acmicpc.net 100,000 * 100,000 을 하면 상당한 메모리를 차지하기 때문에 이중배열을 사용하면 메모리 초과가 발생한다. 고민끝에 슬라이딩윈도우법을 사용하였다. maxdp는 최대값, mindp는 최소값 배열을 나타낸다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util...

https://www.acmicpc.net/problem/1202 1202번: 보석 도둑 첫째 줄에 N과 K가 주어진다. (1 ≤ N, K ≤ 300,000) 다음 N개 줄에는 각 보석의 정보 Mi와 Vi가 주어진다. (0 ≤ Mi, Vi ≤ 1,000,000) 다음 K개 줄에는 가방에 담을 수 있는 최대 무게 Ci가 주어진다. (1 ≤ Ci www.acmicpc.net 내림차순 정렬한 우선순위큐를 이용하여 해결할 수 있었다. 객체를 하나 만들어서 보석의 무게와 가격 속성을 갖는다. 무게순으로 오름차순 정렬한다. 또한 가방도 오름차순 정렬한다. 가방에 넣을 수 있는 보석이라면 큐에 넣고 q.poll()을 하여 result값에 더해준다. import java.io.BufferedReader; import ..

https://www.acmicpc.net/problem/2661 2661번: 좋은수열 첫 번째 줄에 1, 2, 3으로만 이루어져 있는 길이가 N인 좋은 수열들 중에서 가장 작은 수를 나타내는 수열만 출력한다. 수열을 이루는 1, 2, 3들 사이에는 빈칸을 두지 않는다. www.acmicpc.net 백트래킹을 사용하여 해결하면 된다. 연속되는 숫자중에 같은 부분이 있는지 확인하며 수열을 만들어나간다. 제일 작은 수열이므로 가장 먼저 만들어질 것이기에 수열의 길이가 n일 경우 프로그램을 종료시킨다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public class Main { stat..

https://www.acmicpc.net/problem/1021 1021번: 회전하는 큐 첫째 줄에 큐의 크기 N과 뽑아내려고 하는 수의 개수 M이 주어진다. N은 50보다 작거나 같은 자연수이고, M은 N보다 작거나 같은 자연수이다. 둘째 줄에는 지민이가 뽑아내려고 하는 수의 위치가 www.acmicpc.net deque, 즉 덱을 사용하여 문제를 해결하면 된다! 덱의 사이즈의 절반까지의 값중에 해당 값이 존재하면 offerLast() 앞쪽에 없다면 offerFirst()하면 되겠다! import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.LinkedList; ..

https://www.acmicpc.net/problem/1699 1699번: 제곱수의 합 어떤 자연수 N은 그보다 작거나 같은 제곱수들의 합으로 나타낼 수 있다. 예를 들어 11=32+12+12(3개 항)이다. 이런 표현방법은 여러 가지가 될 수 있는데, 11의 경우 11=22+22+12+12+12(5개 항)도 가능하다 www.acmicpc.net index보다 작은 제곱수의 최소합을 확인하여 구해나가면 된다! import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public class Main { public static void main(String[] args) throws Number..

https://www.acmicpc.net/problem/1697 1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net bfs를 이용하여 문제를 해결할 수 있었다. 일차원 배열을 생성하여 index번호에 도달할 수 있는 시간을 저장한다. 따라서 예시에서 수빈이의 위치는 5이고, 동생의 위치는 17이다. 그럼 dp[5]는 0초이다. 그러나 계산하기 쉽게 1로 세팅해준다. 그리고 dp[5-1] , dp[5+1], dp[5*2] 는 1초이다. 계산하기 쉽도록 dp[5]+1을 한다. 만약, 이미..