6-6화이탱

https://www.acmicpc.net/problem/23971 23971번: ZOAC 4 i행 j열 자리를 (i, j)라고 할 때, (1,1)에 참가자가 앉은 경우 다른 참가자는 (1,2), (2,1), (2,2) 자리를 제외한 나머지 자리에 앉을 수 있다. (2,2)의 경우는 (1,1)과 행 번호 및 열 번호의 차가 1보다 크 www.acmicpc.net 백준의 문제집 중 "IT기업 및 대기업 계열사 코테보면서 비슷했던 문제들(지속적으로 업데이트 중)" 문제집의 제일 첫번째 문제이다. 행과 열을 따로 보아, 앉을 수 있는 행,열의 개수를 계산한다. 한 자리를 앉고 n or m만큼 자리를 띄우기 때문에 -> n+1 or m+1 행 or 열길이에 n+1 or m+1이 몇번 들어 갈 수 있는지 -> h..

https://www.acmicpc.net/problem/11286 11286번: 절댓값 힙 첫째 줄에 연산의 개수 N(1≤N≤100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 0이 아니라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0 www.acmicpc.net 우선순위 큐를 사용하여 해결할 수 있었다. 음수일 경우에는 q2에 넣었으며 q2는 내림차순 정렬된 큐이다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Collections; import java.util.PriorityQue..

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/2293 2293번: 동전 1 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. www.acmicpc.net 점화식 dp[j] = dp[j] + dp[j-i번째 동전값] dp[j]는 j원이 될 수 있는 경우의 수를 뜻한다. 1) i=1 dp[1]=dp[1]+dp[1-1]; -> 1 dp[2]=dp[2]+dp[1]; -> 1 . . dp[10]=dp[10]+dp[10-1]; ->1 2) i=2 dp[2]=dp[2]+dp[2-2]; -> 2 dp[3]=dp[3]+dp[3-2];->2 dp[4]=dp[4]+dp..