👩🏻💻 문제링크 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 값이 답이라는 것이다..
PS 연습
👩🏻💻 문제링크 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 ..
👩🏻💻 문제링크 https://www.acmicpc.net/problem/1918 1918번: 후위 표기식 첫째 줄에 중위 표기식이 주어진다. 단 이 수식의 피연산자는 알파벳 대문자로 이루어지며 수식에서 한 번씩만 등장한다. 그리고 -A+B와 같이 -가 가장 앞에 오거나 AB와 같이 *가 생략되는 등의 www.acmicpc.net ✍️ 아이디어 1. 문제 이해 책에서 배운 후위 표기법을 생각하면 되겠구만 우선순위 낮은 녀석(+ , -)이 스택 밑에 깔리고 높은 녀석(* , /)이 위로 올라감 2. 실수한점 : ( 가 나오면 우선순위 상관없이 무조건 스택에 넣었다가 )가 나와야만 연산자가 나올수 있다고 생각함 -> 이러한 생각으로 bool을 이용해서 ( 가 들어온 상태와 안들어온 상태를 나눌려고 했었는데..
👩🏻💻 문제링크 https://www.acmicpc.net/problem/17298 17298번: 오큰수 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다. www.acmicpc.net ✍️ 아이디어 1. 문제 이해 처음엔 스택을 이용하긴 했지만 시간복잡도가 O(N^2)이 나왔다 결국 다른 사람이 문제푼 원리를 보고 O(N)으로 만들었다 2. https://cocoon1787.tistory.com/347 (이 블로그를 보고 아이디어를 얻음) [C/C++] 백준 17298번 - 오큰수 (스택) #include #include #include using namespace st..
