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 문제입니다. 주어진 입력에 대해 i + T 일에 돈이 들어온다고 생각하면 dp[i+T] = max(dp[i + T], current + P) 입니다. 왜냐하면 1번째 날부터 이어온다고 생각하면 현재 벌 수 있는 최대값 current와 i번째 날부터 일을 시작했을 때 버는 돈 P원의 합은 i+T일의 최대 수입은 current+P 또는 dp[i+T] 입니다..
https://www.acmicpc.net/problem/3955 3955번: 캔디 분배 첫째 줄에 테스트 케이스의 개수 t가 주어진다. (0 < t < 100) 각 테스트 케이스는 한 줄로 이루어져 있고, K와 C가 공백으로 구분되어져서 주어진다. (1 ≤ K, C ≤ 109) 선영이는 부자가 아니기 때문에 www.acmicpc.net 한 봉지에 사탕 C개가 들어 있고, 친구들이 K명 올 때 K * X + 1개의 사탕을 준비하여면 몇 봉지의 사탕을 사야하는 지 문제입니다. 문제를 바꿔 생각하면 K * X + 1 = 1 mod K 이므로 결국 A봉지 준비한다면 C * A = 1 mod K 와 동일합니다. 그러므로 유클리드 알고리즘으로 C^-1 mod K를 구하면 됩니다. (10^9 개 넘는 봉지 못 산다..
https://www.acmicpc.net/problem/16946 16946번: 벽 부수고 이동하기 4 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 한 칸에서 다른 칸으로 이동하려면, 두 칸이 인접해야 한다. 두 칸이 www.acmicpc.net 그냥 단순하게 bfs를 돌면 무조건 시간초과가 날 문제입니다. (100만 개 탐색을 100만번....) 그렇기 때문에 다음의 과정을 거쳤습니다. 1. 0으로 연결된 애들의 개수를 세준다. ex. 0 0 0 이런 맵이면 해당 위치는 연결된 0이 3개 이므로 3 3 3이 된다. (그리고 이들은 모두 같은 영역이므로 2번 과정에서 카운트 시 중복되서는 안 됨) 2. 1 위치에서 상..
https://www.acmicpc.net/problem/2668 2668번: 숫자고르기 세로 두 줄, 가로로 N개의 칸으로 이루어진 표가 있다. 첫째 줄의 각 칸에는 정수 1, 2, …, N이 차례대로 들어 있고 둘째 줄의 각 칸에는 1이상 N이하인 정수가 들어 있다. 첫째 줄에서 숫자를 적절 www.acmicpc.net 주어진 입력을 그래프로 생각하여 SCC를 이용해 풀었습니다. 1,2,3,4,5,6,7 3,1,1,5,5,4,6 과 같은 입력일 때 기존 그래프를 1->3 / 2->1 / 3->1 / 4->5 / 5->5 / 6->4 / 7->6 과 같이 생각할 수 있고, 이 때 permutation을 형성하게 된다면 강연결요소 중 하나이고 이러한 것들을 다 뽑는다면 정답에서 원하는 최대의 경우입니다...
https://www.acmicpc.net/problem/1067 1067번: 이동 N개의 수가 있는 X와 Y가 있다. 이때 X나 Y를 순환 이동시킬 수 있다. 순환 이동이란 마지막 원소를 제거하고 그 수를 맨 앞으로 다시 삽입하는 것을 말한다. 예를 들어, {1, 2, 3}을 순환 이동시키면 www.acmicpc.net FFT를 이용해 Convolution 을 구하는 문제입니다. (단순히 브루트포스로 계산하면 최대 60000 * 60000 번 루프 돌아야하므로 시간초과) FFT를 이용해 입력받은 수들을 적용하여 Convolution을 구하기 위해서는 rotation 시킬 다항식을 2배로 적용하고 (ex. a b c d => a b c d a b c d) 곱할 다항식을 reverse 합니다. (ex. a..