👩🏻💻 문제링크 https://www.acmicpc.net/problem/1912 1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net ✍️ 아이디어 1. 문제 이해 연속해서 더할수 있는 수중에 가장 큰 수를 찾자 2. 점화식 D[ i ] = i번째 수로 끝나는 가장 큰 연속합 3. i번째 수열과 i-1번째 점화값과 i번째 수열을 더한 것중에 큰것을 저장한다 A[i] < A[i]+result[i-1] //A[i]는 수열 result는 값 저장 공간 ✍️소스코드 이 아이디어는 강의 안봤으면 절대 안떠올랐을거 같다..(남의 코..
분류 전체보기
👩🏻💻 문제링크 https://www.acmicpc.net/problem/14002 14002번: 가장 긴 증가하는 부분 수열 4 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net ✍️ 아이디어 1. 문제 이해 부분수열 1에서 수열을 출력하는것 까지 함 2. 저장할 배열을 하나 더 만들어서 어떠한 값 때문에 자신의 값이 1 증가 했는지 인덱스를 기록 = 백트래킹 3. 백트래킹 : 해를 찾는 도중 해가 아니어서 막히면, 되돌아가서 다시 해를 찾아가는 기법을 말합니다. 최적화 문..
👩🏻💻 문제링크 https://www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net ✍️ 아이디어 (처음에 아이디어 자체가 생각 안나서 강의 봄) 1. 문제 이해 부분 수열중에서 증가하고 가장 긴것을 찾는 문제 2. 이 문제의 특이한 점은 지금 까지 문제는 맨 마지막에 D[N]이 문제의 답이 되었다면 이 문제는 마지막 D[N]이 답이 아니라 점화식에서 가장 max 값이 답이라는 것이다..
👩🏻💻 문제링크 https://www.acmicpc.net/problem/10844 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net ✍️ 아이디어 1. 문제 이해 계단 수가 되려면 인접한 자리의 수가 1 차이여야 함 2. n-1자리수의 수에서 끝자리가 1차이나는 수를 추가하면 n자리수가 됨 ->n자리수에서 끝에가 0,1,2,...인 경우를 나눔 (long long result[100001][10];) 3. n자리수에서 1은 n-1자리수에서 끝이 0과 2인 수를 더한것과 같다 4. n자리수에서 0, 9 는 예외로 처리 ✍️소스코드 내 코드 #include using namespace std; long long result[1..
👩🏻💻 문제링크 https://www.acmicpc.net/problem/2193 2193번: 이친수 0과 1로만 이루어진 수를 이진수라 한다. 이러한 이진수 중 특별한 성질을 갖는 것들이 있는데, 이들을 이친수(pinary number)라 한다. 이친수는 다음의 성질을 만족한다. 이친수는 0으로 시작하지 않 www.acmicpc.net ✍️ 아이디어 1. 문제 이해 0과 1로 이루어진 수인데 1이 연속해서 나오면 안됨 0으로 숫자가 시작하면 안됨 2. 2차원 dp로 끝자리가 0인 경우와 1인경우를 나눔 0인 경우는 이전 자리수에서 끝이 0,1 둘다와도 되고 1인경우는 이전 자리수에서 끝에가 0이 나와야함 ✍️소스코드 내코드(2차원 dp 사용) #include using namespace std; lo..
👩🏻💻 문제링크 https://www.acmicpc.net/problem/11052 11052번: 카드 구매하기 첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 1,000) 둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1 ≤ Pi ≤ 10,000) www.acmicpc.net ✍️ 아이디어 1. 문제 이해 1장~N장이 들어있는 카드팩이 있는데 N장의 카드를 사기 위해 가장 많은 돈을 지불하는 방법을 구함 2. 처음 내 생각은 1장부터 n-1장까지 가장 많은 돈을 지불하는 경우를 전부 구하면 n장은 저 사이에서 2개를 더한 값과 같을거라 생각함 ✍️소스코드 나의 코드 : 최댓값끼리 더하면 최댓값 나오지 않을까? 라는 반례가 안나와서 그냥 밀어붙임 #includ..
👩🏻💻 문제링크 https://www.acmicpc.net/problem/15990 15990번: 1, 2, 3 더하기 5 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 1,000,000,009로 나눈 나머지를 출력한다. www.acmicpc.net ✍️ 아이디어 1. 1,2,3의 합 1과 같이 result[i-3] + result[i-2] + result[i-1] 에 i-1에서 마지막이 1인거, i-2에서 마지막이 2인거, i-3에서 마지막이 3인것을 빼줘야 한다고 생각은 함. 2. 하지만 어뜨케 구현해야할지 생각을 못함(2차원배열을 어케 생각해;;) 3. 예외 처리로 [1], [2], [3]에 해당하는 배열을 초기화 하였다 ✍️소스코드 나의 풀이 #include using..
👩🏻💻 문제링크 https://www.acmicpc.net/problem/11726 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net ✍️ 아이디어 1. 문제 이해 문제를 해석하던 도중 단순화 해보니까 n을 1과 2의 합으로 나타낼수 있는 경우의 수였다 그리고 n을 1부터 6까지 나열하여 이게 피보나치 수열과 같은 형태라는것을 알게되었다 -> 하지만 이것이 왜 피보나치 수열과 같은 형태가 나오는지는 이해하지 못했다 2. 점화식 : 직접 써보면 나옴 = 피보나치 수열 ✍️소스코드 (A + B) % M = (A%M + B%M) % M ..
