https://www.acmicpc.net/problem/26093 26093번: 고양이 목에 리본 달기 첫 번째 줄에는 고양이의 수 $N$과 리본 종류의 수 $K$가 공백으로 구분되어 주어진다. $(1 \leq N \leq 100, 2 \leq K \leq 10\,000)$ 다음 $N$개의 줄에는 각각 $K$개의 정수 $a_{i,1}, \cdots, a_{i,k}$이 공백으로 구 www.acmicpc.net 양 옆에 위치한 고양이와 방울의 종류가 같지 않도록 함과 동시에 만족도를 최고로 높이는 방법을 찾아야한다. 그래서 접근한 방법은 단순히 이전 고양이의 가장 높은 만족도의 방울 번호와 다음으로 높은 만족도의 방울 번호를 저장하여 현재 순서의 고양이의 방울 번호와 비교하여 만족도의 합을 저장하는 방식이..
dp
https://www.acmicpc.net/problem/19576 19576번: 약수 가능 한 방법 중 하나로, a2를 12로, a3을 3으로 바꾸면 된다. www.acmicpc.net 임의의 수 x, y를 잡았을 때, x%y == 0 이거나 y % x == 0이 되도록 수열 내의 원소를 바꾸어야하는데, 바꾸는 횟수가 최소가 되어야한다. 처음 접근했던 방식은 N의 범위가 1 ~ 5000이므로 반복문을 돌려 약수의 개수가 가장 많은 원소를 찾고, 해당 원소와 나누어지지 않는 원소를 바꾸는 방식이다. 그런데 코드를 돌려보니, 5 5 7 7 35 와 같은 원소가 주어졌을 때 제대로 출력이 되지 않는다는 것을 확인했고, 그래서 똑같이 반복문을 돌리되, 이번엔 약수의 개수가 아니라 나누어떨어지는 수의 개수를 구..
https://www.acmicpc.net/problem/1351 1351번: 무한 수열 첫째 줄에 3개의 정수 N, P, Q가 주어진다. www.acmicpc.net A0는 1로 주어지고, Ai ~ An은 주어지지 않았다. 대신 점화식으로 Ai = Ai/p + Ai/q인데, p와 q 값이 난수이다. 그러므로 확정적으로 아는 값은 A0뿐이고, p와 q에 따라 Ai의 값이 변한다. 먼저 예제 1번을 가지고 규칙을 찾아보았다. N = 7, P = 2, Q = 3의 입력이 주어졌을 때, Ai는 아래와 같다. A0 = 1 A1 = A0 + A0 = 2 A2 = A1 + A0 = 3 A3 = A1 + A1 = 4 A4 = A2 + A1 = 5 A5 = A2 + A1 = 5 A6 = A3 + A2 = 7 A7 = ..
https://www.acmicpc.net/problem/7570 7570번: 줄 세우기 입력은 2 개의 줄로 이루어져 있다. 첫 줄에는 어린이 수를 나타내는 정수가 주어진다. 둘째 줄에는 처음에 줄서있는 어린이들의 번호가 차례대로 주어진다. 주어진 번호들 사이에는 공백이 하 www.acmicpc.net 처음 문제를 읽었을 때 들었던 생각은 단순히 가장 긴 증가하는 부분 수열이었다. 그래서 열심히 LIS 코드를 짰는데, 이상하게 원하는 결과값이 출력이 되지 않았다. 그래서 임의로 사용한 예제 9 1 7 9 8 3 2 4 5 6 9 9 4 7 1 3 2 6 8 5 9 9 8 7 6 5 4 3 2 1 9 1 2 3 4 9 8 7 6 5 9 9 8 7 6 5 4 3 1 2 9 9 8 7 5 6 4 3 2 1 ..
https://www.acmicpc.net/problem/2602 2602번: 돌다리 건너기 첫째 줄에는 마법의 두루마리에 적힌 문자열(R, I, N, G, S 로만 구성된)이 주어진다. 이 문자열의 길이는 최소 1, 최대 20 이다. 그 다음 줄에는 각각 와 를 나타내는 www.acmicpc.net dp + dfs로 문제를 해결했다. 일단 처음에는 돌의 개수 100개, 문자 개수 20개, 천사와 악마 시작으로 2개가 존재하길래 재귀를 이용한 완전 탐색으로 접근했다. 그런데 코드를 짜면서 볼때는 몰랐는데, 시간초과가 난다고 해서 급히 노선을 바꾸었다. 시간초과가 나는 이유는 나중에 알았는데 (질문), 돌 100개, 문자열 20개가 모두 같은 언어로 이루어지면 결국 2 * 100 C 20이 되기 때문이었다..
