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 사용해서 해결했다. dp[i] 를 i일째 시점에서 상담을 끝냈을 때의 최대 이익으로 정의한다. i일째에 상담을 진행한 경우는 dp[i+T[i]] 를 dp[i] + P[i] 로 갱신 할 수 있으며, 이때 편의상 T[i]와 P[i] 를 0부터 시작하는 인덱스로 관리해주면 소스코드가 깔끔해진다. 상담을 진행하지 않더라도, 지난 일자에서의 최대 수익을 그대로 가져와서 ..
https://www.acmicpc.net/problem/1613 1613번: 역사 첫째 줄에 첫 줄에 사건의 개수 n(400 이하의 자연수)과 알고 있는 사건의 전후 관계의 개수 k(50,000 이하의 자연수)가 주어진다. 다음 k줄에는 전후 관계를 알고 있는 두 사건의 번호가 주어진다. www.acmicpc.net 바로 앞서 풀었던 문제와 동일한 유형 앞선 문제에서 태그를 까봤더니 플로이드-와샬이더라... arr[a][b] 를 a가 b 앞에 오는 사건인지 체크하는 용도로 사용한다. 플로이드 와셜을 통해서 모든 a,b 쌍들에 대해서 사건 간의 전후관계를 설정해 주고, 정답을 출력할 때 arr[a][b] 가 true라면 앞서는 것이고, arr[b][a] 가 true라면 뒤에 오는 사건인 것이고, 둘 다 ..
https://www.acmicpc.net/problem/16929 16929번: Two Dots 첫째 줄에 게임판의 크기 N, M이 주어진다. 둘째 줄부터 N개의 줄에 게임판의 상태가 주어진다. 게임판은 모두 점으로 가득차 있고, 게임판의 상태는 점의 색을 의미한다. 점의 색은 알파벳 대문 www.acmicpc.net 그래프에서 사이클을 찾아내는 문제. DFS로 접근했다. dfs를 진행할때, 바로 전에 지나고 있던 점의 위치를 px, py에 담아놓아서, 탐색한 다음 뒤를 돌아서 다시 탐색하는것을 막아준다. 보통은 방문 여부를 저장하는 vis 배열을 통해서 재탐색을 막아주는데, 방문여부를 통해서 재탐색을 막을 수 없는 이유로 문제에서 요구하고 있는 것이 "방문한 적이 있던 같은 점의 색을 가진 위치" 로..
https://www.acmicpc.net/problem/14719 14719번: 빗물 첫 번째 줄에는 2차원 세계의 세로 길이 H과 2차원 세계의 가로 길이 W가 주어진다. (1 ≤ H, W ≤ 500) 두 번째 줄에는 블록이 쌓인 높이를 의미하는 0이상 H이하의 정수가 2차원 세계의 맨 왼쪽 위치 www.acmicpc.net 브루트포스 문제이다. 어떠한 위치 i에서 고일수 있는 물의 양은, 그 양쪽으로 i보다 높이가 높은 두개의 블록 l,r 이 있을때, min(l,r) - i 만큼 고일 수 있다. 모든 i에 대해서 순회하는데 O(N), 높이가 최대로 높은 두 블록 l,r 을 찾는데 O(N)으로 전체 시간복잡도는 O(N^2) 이다. 위치 i에서 l,r을 찾고자 할때, l이나 r이 존재하지 않는 경우가 ..
https://www.acmicpc.net/problem/2473 2473번: 세 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 3 이상 5,000 이하의 정수이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 www.acmicpc.net 이분탐색 문제이다. 세 수를 선정할 때에, O(N^3) 브루트포싱으로 접근하면 시간초과를 받게 되므로 세 숫자 중 하나는 이분탐색을 통해서 골라내야 한다. O(N^2) 로 두개의 쌍을 더해서 그 합 SUM 을 만들어 주고, SUM의 음수와 가장 가까운 수를 이분탐색으로 구해준 다음 셋의 합이 0에 가까워지도록 갱신해나가면 된다. 이때, lower_bound로 구한 인덱스가 k..
https://www.acmicpc.net/problem/13975 13975번: 파일 합치기 3 프로그램은 표준 입력에서 입력 데이터를 받는다. 프로그램의 입력은 T개의 테스트 데이터로 이루어져 있는데, T는 입력의 맨 첫 줄에 주어진다.각 테스트 데이터는 두 개의 행으로 주어지는데, www.acmicpc.net 우선순위 큐 사용 문제. 하나의 우선순위 큐에 임시파일을 포함한 모든 파일들을 저장해놓고, 실시간으로 가장 비용이 작은 두개의 파일을 합쳐서 하나의 임시파일로 만들어주면 된다. 이 과정을 파일이 하나만 남을때까지 반복해주면 되고, 전체 시간복잡도는 O(KlogK) 이다. 입력되는 수의 갯수가 1e6으로 꽤나 많으니 fastio를 써야 할 듯 하고, 수의 범위가 int값을 넘어가니까 long l..