알고리즘,PS

https://www.acmicpc.net/problem/2579 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net 문제 풀이 포도주시식 문제랑 비슷하다. 단 , 종결 조건이 정해져있다. 만약 n번째 계단을 갔다고 가정하면 갈 수 있는 경우의 수는 두 가지다. dp[i] 를 i번째 계단까지 갔을 때 , 얻을 수 있는 점수의 총 합이라고 가정하자. 1. 직전 계단을 밟는경우 연속 3번 계단을 건널 수 없으니 => dp[n] = dp[n-3] + n-1계단점수 + n계단 점수 2. 한칸 건너 뛰어 오는 경우 => dp[n] =..

https://www.acmicpc.net/problem/2156 2156번: 포도주 시식 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규 www.acmicpc.net 문제 풀이 조건이 있는 DP 문제이다. 특정 i 번째 포도주를 골랐다는 가정을 하면 두 가지 경우로 나뉜다. i-1 번째를 선택한 경우 => dp[i] =dp[i-3]+arr[i-1]+arr[i] i-1 번째를 선택하지 않은 경우 => dp[i] = dp[i-2] + arr[i] 그리고 누적합이 그 전 단계가 더 클 경우도 있기때문에 dp[i] 와 dp[i-1] 중 큰 것을 골라야한다. 1 2 3 ..

https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 문제 풀이 만약 구하고 싶은 수를 i 라고 하면 , min( dp[i/2]+1 , dp[i/3]+1 , dp[i-1]+1 ) 이라는 최적해를 구해서 하면된다. 연산 순서에 따라 완전 다른 횟수가 나올 수 있기 때문에 그리디로 접근하면 x 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 import java.util.*; import java.io.*; public class Main{ public static void main(Strin..

https://www.acmicpc.net/problem/1946 1946번: 신입 사원 첫째 줄에는 테스트 케이스의 개수 T(1 ≤ T ≤ 20)가 주어진다. 각 테스트 케이스의 첫째 줄에 지원자의 숫자 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개 줄에는 각각의 지원자의 서류심사 성 www.acmicpc.net 문제 풀이 그리디 문제이다.. 처음엔 lis 알고리즘으로 풀 수 있을줄 알았다 ..왜냐 .. 서류와 면접 성적이 둘다 낮아야한다 => 평행하다 => 증가하는수열 => LIS 알고리즘 하지만 반례가 있었고 , LIS로 풀 수 없다는 것을 깨달았다 .. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27..

https://www.acmicpc.net/problem/2252 2252번: 줄 세우기 첫째 줄에 N(1 ≤ N ≤ 32,000), M(1 ≤ M ≤ 100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의 www.acmicpc.net 문제 풀이 위상 정렬 문제이다. inDegree 배열을 하나 만든 다음 , 차수가 0이면 Queue에 추가 , 인접한 노드들의 InDegree 차수 1씩 감소 하는식으로 Queue가 비어 있을때 까지 반복하면 된다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 ..

https://www.acmicpc.net/problem/1197 1197번: 최소 스패닝 트리 첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 www.acmicpc.net 문제 풀이 크루스칼 알고리즘을 이용한 최소 신장트리를 구하는 문제이다. Edge를 weight가 작은 순으로 Queue에 넣은 뒤 ( priorityQueue사용) parent 배열의 크기를 정점의 갯수만큼 정해주고 , union연산으로 disjointSet을 만들어가면서 가중치를 더하는 식으로 하면 된다. 1 2 3 4 5 6 7 8 9 10 11 ..

https://www.acmicpc.net/problem/1806 1806번: 부분합 첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다. www.acmicpc.net 문제 풀이 투 포인터 활용 문제이다. start, end를 0에서 시작하여 목표값 target 보다 크거나 같으면 start 전진, target이 더 크면 end 전진 , end가 전진하다가 끝에 다다르면 종료. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 import java.uti..

https://www.acmicpc.net/problem/3273 3273번: 두 수의 합 n개의 서로 다른 양의 정수 a1, a2, ..., an으로 이루어진 수열이 있다. ai의 값은 1보다 크거나 같고, 1000000보다 작거나 같은 자연수이다. 자연수 x가 주어졌을 때, ai + aj = x (1 ≤ i < j ≤ n)을 만족하는 www.acmicpc.net 문제 풀이 투포인터를 써야하는 문제이다. i < j 를 항상 만족해야 하므로 , start < end 가 만족해야한다. 이걸 안해서 틀렸었음 .. 1. 정렬된 배열이 필요. 2. 왼쪽맨끝 과 오른쪽 맨끝에서 순차적으로 번갈아 가면서 조금씩 접근 조건을 만족한다면 end,start 인덱스 동시에 조정 조건을 만족하지 않는다면 둘 중 하나만 조정..