📙 Algorithm Solving/Java

https://www.acmicpc.net/problem/10978문제 요약N명의 학생이 있고 N개의 기숙사가 있다모든 학생들은 본인이 살았던 봄학기 기숙사에서 가을 학기에 다른 기숙사로 배정되면 이사를 해야하므로 기숙사 재배정을 신청하였다이렇게 모든 학생들은 기숙사 재배정을 신청했지만, 학생복지팀에서는 어떤 학생에게도 기숙사 재배정을 해주지 않으려고 한다.봄학기때 기숙사를 이미 배정받은 상태에서, 가을학기 기숙사에 아무도 재배정이 되지 않는 경우의 수를 구해보자시간 제한1초입력첫 번째 줄에 테스트 케이스의 수 T가 주어진다.각 케이스의 첫 번째 줄에 학생 명수(기숙사의 개수) N (1 ≤ N ≤ 20) 이 주어진다.출력각 테스트 케이스 별로 아무도 재배정이 되지 않는 경우의 수를 출력한다.접근법문제를 ..

https://www.acmicpc.net/problem/13144문제 요약길이가 N인 수열이 주어질 때, 수열에서 연속한 1개 이상의 수를 뽑았을 때 같은 수가 여러 번 등장하지 않는 경우의 수를 구하는 프로그램을 작성시간 제한1초입력첫 번째 줄에는 수열의 길이 N이 주어진다. (1 ≤ N ≤ 100,000)두 번째 줄에는 수열을 나타내는 N개의 정수가 주어진다.수열에 나타나는 수는 모두 1 이상 100,000 이하이다.출력조건을 만족하는 경우의 수를 출력접근법먼저 정답 변수에 연속부분수열 길이가 1인 개수를 미리 더해줌이후는 투포인터로 가능한 개수를 구하려고 했다.s = 0, e = 1부터 시작여기서 e가 가리키는 숫자를 포함한 연속 부분 수열의 개수는 e보다 앞에 있는 숫자들의 개수에 영향을 받는다..

https://www.acmicpc.net/problem/30461문제 요약N * M 의 공간이 존재하고, 각 칸에는 물고기 여럿이 존재가방 먼 칸은 (N, M)무게가 a인 무게추를 매달아 b만큼 힘으로 던지면 (a,b)칸에 미끼가 존재이때, (a,b)에 존재하는 미끼는 1 ≤ i ≤ a인 모든 정수 i에 대해서 (i,b)에 존재하는 모든 물고리를 사로 잡는다.만약 낚싯줄을 한 바퀴 감아 올리면, (a,b)에 위치한 미끼는 (a-1,b-1)로 이동하고, 이동한위치에서 물고기를 사로잡는다.이때, 무게추의 무게와 낚싯대를 휘두를 힘을 알려줄 때마다, 낚싯대를 휘두른 뒤 회수할 때까지 낚싯줄을 감아올리면 몇 마리의 물고기가 사로잡힐지 구해라시간 제한2초입력일감호의 크기를 나타내는 정수 N, M과 낚싯대를 휘두..

https://www.acmicpc.net/problem/14527문제 요약M마리의 소(짝수마리) M/2쌍으로 나누어 각각의 쌍으로 나누어 동시에 젖을 짜는 외양간으로 보내려고 한다.각 외양간에서 두 소의 젖을 짜는 데 걸리는 시간은 두 소의 젖 생산량의 합과 같다.즉, 젖을 짜는 시간이 각 쌍의 소들의 젖 생산량의 합에 따라 달라진다.최적의 소 짝을 찾아 젖 짜는 작업을 완료하는 최소 시간을 계산하라시간 제한2초입력N개의 줄이 주어지며 각 줄에는 x와 y가 주어진다x는 y 단위의 젖 생산량을 가진 소들의 수를 의미M은 x들의 총합으로, 즉 모든 소들의 총합1 ≤ N ≤ 10만1 ≤ y ≤ 10억출력젖 짜는 작업을 완료하는 데 걸리는 최소 시간을 출력접근법주어질 수 있는 소 마리수의 총합 M은 10억 개..

https://www.acmicpc.net/problem/17208문제 요약주방에 남은 치즈버거와 감자튀김으로 주문을 처리하려고 한다모든 주문은 각각 치즈버거 요구 개수와 감자튀김 요구 개수를 의미하는 2개의 정수로 이루어진다주문이 들어온 순서와 관계없이 원하는 주문을 선택해 처리할 수 있다최선의 방법으로 주문을 선택해 처리한다면 최대 몇 개의 주문을 처리할 수 있을까시간 제한3초입력첫째 줄에 주문의 수 N(1 ≤ N ≤ 100), 주방에 남은 치즈버거 개수 M(1 ≤ M ≤ 300), 주방에 남은 감자튀김 개수 K(1 ≤ K ≤ 300)가 주어진다둘째 줄부터 N개의 줄에는 주문 내용을 의미하는 두 정수 x, y (1 ≤ x, y ≤ 300)가 주어진다x는 치즈버거 요구 개수, y는 감자튀김 요구 개수를..

https://www.acmicpc.net/problem/16929문제 요약N*M크기의 게임판 위에서 진행점 K개 d1, …, dk로 이루어진 사이클 정의는 아래와 같다모든 k개의 점은 서로 다르다k는 4보다 크거나 같다모든 점의 색은 같다모든 1 ≤ i ≤ k-1에 대해서, di와 di+1은 인접한다.또, dk와 d1도 인접한다.두 점이 인접하다는 것은 각각 점이 들어있는 칸이 변을 공유한다는 의미게임판 상태가 주어질 때, 사이클이 존재하는지 아닌지 구하라시간 제한2초입력게임판의 크기 N, M2 ≤ N, M ≤ 50N개의 줄에 게임판 상태가 주어진다.게임판의 상태는 점의 색을 의미점의 색은 알파벳 대문자 한 글자출력사이클이 존재하면 YES, 없다면 NO 출력접근법DFS알고리즘으로 한 정점에서 출발해, ..

https://www.acmicpc.net/problem/27945문제 요약1번부터 N번까지의 요리 학원이 존재요리 학원 사이에는 M개의 양방향길이 존재키위새는 이제 매일 노점에 들러 가지 디저트를 먹지 않으면 쓰러지게 된다N - 1개의 길을 골랐을 때, 키위새가 쓰러지는 날을 d일 차로 할 때, d의 최댓값 구하기시간 제한1초입력요리학원 수 N과 길의 수 M1 ≤ N ≤ 10만M개의 줄에 연결된 두 학원의 번호와 노점이 여는날 ti가 주어짐각 요리 학원에서 길을 따라 모든 요리 학원으로 가는 방법이 존재하는 경우만 주어진다.두 요리 학원 사이의 길은 많아야 하나이다ti는 모두 다르다출력d의 최댓값 출력접근법키위새는 1일차부터 매일매일 길 사이에 위치한 노점에 방문해야 하고, N-1개의 길만 갈 수 있다..

https://www.acmicpc.net/problem/1863문제 요약주어진 스카이라인 정보를 보고 건물이 최소 몇 채인지 알아내라시간 제한2초입력첫째 줄에 n이 주어진다. (1 ≤ n ≤ 50,000)다음 n개의 줄에는 왼쪽부터 스카이라인을 보아 갈 때 스카이라인의 고도가 바뀌는 지점의 좌표 x와 y(1 ≤ x ≤ 1,000,000. 0 ≤ y ≤ 500,000)첫 번째 지점의 x좌표는 항상 1이다.출력첫 줄에 최소 건물 개수를 출력접근법스택이 오름차순 스택을 유지하도록 담기만약 다음에 올 원소가 스택의 상단에 있는 값보다 작거나 같다면, pop시도이때, 카운트는 다음 원소보다 큰 원소를 pop할 때만 카운트마지막에 스택이 비어있지 않다면, 남은 높이가 0보다 큰 원소개수만큼만 추가로 카운트코드im..

https://www.acmicpc.net/problem/1461문제 요약세준이는 현재 0에 위치책들도 0에 위치각 책들의 원래 위치가 주어질 때, 책을 모두 제자리에 둘 때 드는 최소 걸음수는?마지막에 0으로 돌아올 필요 X한 번에 최대 M권의 책을 들 수 있음시간 제한2초입력책의 개수 N과 한 번에 들 수 있는 책 개수 MN과 M은 50이하 자연수책의 원래 위치가 주어진다.0인 경우는 없으며, -10000~10000 범위 내 정수출력다 정리하는 데 필요한 최소 걸음 수 출력접근법테케1M = 2책 원래 위치(정렬) : -1 0 3 4 5 6 114번, 5번 책 두고 오기 ⇒ 5 + 5 = 10-1번 책 두고 오기 ⇒ 1 + 1 = 23번 책 두고 오기 ⇒ 3 + 3 = 66번, 11번 책 두기 ⇒ 11..

https://www.acmicpc.net/problem/2662문제 요약만원 단위로 각 기업에 투자할 수 있다돈을 투자하게 되면 얻게되는 이익도 있다.투자액이 정해져 있고, 기업의 개수와 각 기업에 투자했을 때 얻는 이익이 주어질 때, 가장 많이 얻을 수 있는 투자방식과 그때의 이익금을 구하라시간 제한1초입력투자 금액 N과 투자 가능한 기업들 개수 M1 ≤ N ≤ 300, 1 ≤ M ≤ 20N개의 줄에 투자액수와 각 기업이 투자가에게 주는 이익이 주어진다.투자 금액은 항상 1~N같은 투자금액이 두 번이상 주어지지 X ⇒ i번째 줄에 주어지는 투자 금액은 i-1만원출력얻을 수 있는 최대 이익 출력각 기업에 투자한 액수 출력접근법재귀DP로 접근했고, 매개 변수로 현재 갖고 있는 금액 remain과 현재 가..