https://www.acmicpc.net/problem/2225 2225번: 합분해 첫째 줄에 답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net DP 문제다. 처음 생각한 방법은 2차원 배열을 이용해 1을 포함해 1개로 n을 만드는 경우의 수 2를 포함해 1개로 n을 만드는 경우의 수 ... 1을 포함해 2개로 n을 만드는 경우의 수 2를 포함해 2개로 n을 만드는 경우의 수 ... ... ... ... 이렇게 배열 자체를 n을 구하기 위한 경우의 수를 구하려 했다. 겹치는 부분을 생각할 수도 없고 규칙도 찾기 어려워 버렸다. 두 번째 생각한 방법은 모든 경우의 수를 다 적고 거기에서 규칙적인 변화를 찾았다. 작은 규칙을 찾긴 했지만 사용할 수 있는 방법이 없고, ..
Algorithm
https://www.acmicpc.net/problem/2138 2138번: 전구와 스위치 N개의 스위치와 N개의 전구가 있다. 각각의 전구는 켜져 있는 상태와 꺼져 있는 상태 중 하나의 상태를 가진다. i(1 < i < N)번 스위치를 누르면 i-1, i, i+1의 세 개의 전구의 상태가 바뀐다. 즉, 꺼져 www.acmicpc.net 그리디 문제다. 스위치를 작동하는 가장 효율적인 방법은 순차적으로 탐색하되 지나간 전구는 건드리지 않는 것이다. 즉, n번째 전구를 바꾸기 위해서는 n+1번째 스위치를 작동하는 것이다. 이 방법으로 문제를 해결하려고 하면 첫 번째 스위치에 대한 의문이 생긴다. 첫 번째 스위치는 이전 전구가 존재하지 않으므로 작동 여부를 판별할 수 없다. 때문에 전구 탐색을 두 번 진행..
https://www.acmicpc.net/problem/1946 1946번: 신입 사원 첫째 줄에는 테스트 케이스의 개수 T(1 ≤ T ≤ 20)가 주어진다. 각 테스트 케이스의 첫째 줄에 지원자의 숫자 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개 줄에는 각각의 지원자의 서류심사 성 www.acmicpc.net 그리디 문제다. 두 사람의 두 점수를 비교 했을 때 한 점수는 낮고 한 점수는 높아야 한다. 두 등수 중 하나를 기준으로 정렬하고 다른 등수가 전 사람보다 높은지 판별하면 된다. 등수는 중복되지 않으니 정렬을 사용하지 않고 하나의 등수를 인덱스로 사용해도 된다. #include #include using namespace std; pair arr[100000]; int mai..
https://www.acmicpc.net/problem/20057 20057번: 마법사 상어와 토네이도 마법사 상어가 토네이도를 배웠고, 오늘은 토네이도를 크기가 N×N인 격자로 나누어진 모래밭에서 연습하려고 한다. 위치 (r, c)는 격자의 r행 c열을 의미하고, A[r][c]는 (r, c)에 있는 모래의 양을 www.acmicpc.net 구현 문제다. 깊게 생각해야 할 부분은 없었고 문제대로 바로 구현했다. 방향이 바뀌는 점을 어떻게 처리해야 하는지 고민이었다. 4방향 좌(1) 하(2) 우(3) 상(4) 으로 나눠서 하나하나 구현했다. 방향이 변해도 흩어지는 비율은 같기 때문에 해당 배열은 한 번만 선언했다. 토네이도는 1칸 (방향전환) 1칸(방향전환) 2칸 (방향전환) 2칸 (방향전환) 3칸 ....
https://www.acmicpc.net/problem/20056 20056번: 마법사 상어와 파이어볼 첫째 줄에 N, M, K가 주어진다. 둘째 줄부터 M개의 줄에 파이어볼의 정보가 한 줄에 하나씩 주어진다. 파이어볼의 정보는 다섯 정수 ri, ci, mi, si, di로 이루어져 있다. 서로 다른 두 파이어볼의 위치 www.acmicpc.net 구현 문제다. 나도 내가 뭘 했는지 모르겠다. #include #include #include using namespace std; struct fire { int r; int c; int m; int s; int d; }; vector board[51][51]; vector visit; int v[51][51]; int N, M, K; int main() ..
https://www.acmicpc.net/problem/2294 2294번: 동전 2 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. 가치가 같은 동전이 여러 번 주 www.acmicpc.net DP 문제다. 이전 값들의 접근으로 배열을 이용했다. 입력 받은 가치들을 배열에 저장하고 그 값들을 탐색했다. 동전의 가치를 더해서 원하는 수를 만들 수 있기 때문에 dp[원하는 값 - 가치] + 1을 하면 그 값을 만들기 위한 동전의 수를 알 수 있다. 모든 가치의 값들을 탐색하면서 그 중 최솟값을 찾는다. 주의할 점은 1. 배열의 범위를 벗어나선 안된다. 즉, 원..
