https://www.acmicpc.net/problem/11660 11660번: 구간 합 구하기 5 첫째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다. (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000) 둘째 줄부터 N개의 줄에는 표에 채워져 있는 수가 1행부터 차례대로 주어진다. 다음 M개의 줄에는 네 www.acmicpc.net x1, y1 부터 x2, y2 까지의 합을 구하는 문제입니다. 얼핏보면 n이 최대 1024라 그냥 다 더하면 될 거 같지만 100000번 수행해야 하므로 브루트포스로는 안 됩니다. dp를 이용해 1,1부터 x,y까지의 합을 먼저 구하면 다음과 같습니다. dp[i][j] = num + dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1] (..
https://www.acmicpc.net/problem/2210 2210번: 숫자판 점프 111111, 111112, 111121, 111211, 111212, 112111, 112121, 121111, 121112, 121211, 121212, 211111, 211121, 212111, 212121 이 가능한 경우들이다. www.acmicpc.net 5 x 5 숫자판을 돌아다니면서 6자리 수를 만들 수 있는 경우의 수를 구하는 문제입니다. 조건으로 중복해서 같은 위치를 지날 수 있음에 주의해야 합니다. 판 자체가 5 x 5로 작은 편이므로 특별한 조건 없이 bfs를 진행할 수 있습니다. bfs를 통해 각 위치를 출발점으로 6자리를 계속 만들어가면서 6자리가 만들어졌을 때 set에 넣습니다. 그러면 s..
https://www.acmicpc.net/problem/12904 12904번: A와 B 수빈이는 A와 B로만 이루어진 영어 단어가 존재한다는 사실에 놀랐다. 대표적인 예로 AB (Abdominal의 약자), BAA (양의 울음 소리), AA (용암의 종류), ABBA (스웨덴 팝 그룹)이 있다. 이런 사실에 놀란 수 www.acmicpc.net A,B로만 이루어진 문자열이 주어졌을 때 1. 문자열 뒤에 A 붙이기 2. 뒤집고 B 붙이기 2가지 연산이 가능합니다. 이 때 주어진 문자열 S로 T를 만들 수 있는지 확인하는 문제입니다. 문제를 반대로 생각하면, T의 마지막이 A이면 A를 떼버리고, 마지막이 B이면 떼고 뒤집으면 됩니다. 그리고 S와 비교하여 같은지 아닌지 판단하면 됩니다. 코드는 다음과 같..
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 개 넘는 봉지 못 산다..