DP6 9465 스티커 https://www.acmicpc.net/problem/9465 9465번: 스티커 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 두 줄에는 n개의 정수가 주어지며, 각 정수는 그 위치에 해당하는 스티커의 www.acmicpc.net 접근 RGB문제와 유사한 문제여서 매우 쉽게 풀었다. 스티커를 떼면 상하좌우에 있는 스티커들은 쓸 수가 없다. 최대한 많은 가치의 스티커를 떼어보자는 거다. 왼쪽부터 스티커를 뜯는다고 생각하자. 직전에 어떻게 뜯었냐에 따라 다음 스티커의 운명이 정해진다. 직전에 아래쪽 스티커를 떼어냈다면 다음 열의 아래쪽 스티커는 뜯을 수 없다. 따라서, 윗쪽 스티커를 떼어내기 또는 스티커를 떼지 않는.. 2022. 9. 10. 2502 떡 먹는 호랑이 https://www.acmicpc.net/problem/2502 2502번: 떡 먹는 호랑이 첫줄에 첫 날에 준 떡의 개수 A를 출력하고 그 다음 둘째 줄에는 둘째 날에 준 떡의 개수 B를 출력한다. 이 문제에서 주어진 D, K에 대해서는 항상 정수 A, B (1≤ A ≤ B)가 존재한다. www.acmicpc.net 사실 골드 문제를 풀다가 현타가 와서 실버 문제를 찾게 되었다... 열심히 해야겠다. 접근 호랑이에게 떡을 주는 방법은 어제 준 떡 갯수 + 그저께 준 떡 갯수이다. 피보나치와 똑같은데 문제는 첫 날과 둘째 날에 떡을 몇 개 줬는지 모르고, D번째 날에 K개 만큼 줬다고 한다. 어떤 공식으로 한 번에 풀리지 않을 것 같아 예시를 써보기로 했다. 첫 날에 준 떡 갯수를 //[a]//, 둘째.. 2022. 9. 7. 4811 알약 https://www.acmicpc.net/problem/4811 4811번: 알약 입력은 최대 1000개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄이며, 병에 들어있는 약의 개수 N ≤ 30 가 주어진다. 입력의 마지막 줄에는 0이 하나 주어진다. www.acmicpc.net 접근 분명히 이전에 계산한 값을 활용하는게 DP일텐데... 점화식이 어렴풋이 보이는 것 같기도 하고... 문제 이해를 잘 못해 2N일이 지나면 조합의 개수가 2N개인줄 알고 예시를 만들어봐도 안되길래 뭐가 문젠가 싶어 문제를 제대로 읽어보았다. 1. 첫째 날에 알약통에서 온전한 알약 한 조각을 반으로 나눠 하나를 먹고 나머지는 다시 알약통에 넣는다. 2. 둘째 날에 알약통에서 알약 하나를 꺼낸다. 2-1. 온전한.. 2022. 9. 2. 2226 이진수 https://www.acmicpc.net/problem/2226 2226번: 이진수 0과 1로 구성된 이진수가 있다. 이 이진수에서 0을 10으로, 1을 01로 동시에 치환하면 길이가 두 배인 이진수를 얻을 수 있다. 이러한 이진수들을 차례로 나열하면 하나의 이진수 수열이 된다. 편의 www.acmicpc.net 문제에서 말하는 대로 처음 몇 개의 이진수들을 구해보면 아래처럼 나오게 된다. 0 x 1 1 2 01 3 1001 4 01101001 5 1001011001101001 6 01101001100101101001011001101001 7 1001011001101001011010011001011001101001100101101001011001101001 ... dp는 이전에 구했었던 결과를 이용한다.. 2022. 8. 29. 2293 동전 1 https://www.acmicpc.net/problem/2293 2293번: 동전 1 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. www.acmicpc.net 배낭문제의 아류처럼 보이는데, 예전에 했었던 코드들을 살펴봐도 도저히 몰랐다. 지금까지 풀어본 문제중에 비슷했던 것은 N개의 동전들로 K원을 만들 때 최소개수를 구하는 문제였다. 하지만 이 문제는 경우의 수를 구하는 문제여서 매우 헷갈렸다. 10번이나 틀리며 한참 고민한 끝에 상당히 간단한 문제임을 깨달았다. 설명이 난잡하기 때문에 더 좋은 블로그를 소개해야겠다. https://gurumee92.t.. 2022. 8. 17. 2225 합분해 https://www.acmicpc.net/problem/2225 [2225번: 합분해 첫째 줄에 답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net](https://www.acmicpc.net/problem/2225) 문제가 말하는 대로 합분해를 해보았다. 예를 들어서 0부터 6까지의 정수들 중에 2개를 사용해 6을 만든다고 했을 때 다음과 같은 조합이 나온다. 0 6 1 5 2 4 3 3 4 2 5 1 6 0 여기서 더 나아가 0부터 6까지의 정수들 중에 3개를 사용해 6을 만든다고 했을 때, 다음과 같은 조합을 볼 수 있다. 0 0 6 0 1 5 0 2 4 0 3 3 0 4 2 0 5 1 0 6 0 1 0 5 1 1 4 1 2 3 1 3 2 1 4 1 1 5 0 .. 2022. 8. 14. 이전 1 다음