Mini

https://www.acmicpc.net/problem/1699 1699번: 제곱수의 합 어떤 자연수 N은 그보다 작거나 같은 제곱수들의 합으로 나타낼 수 있다. 예를 들어 11=32+12+12(3개 항)이다. 이런 표현방법은 여러 가지가 될 수 있는데, 11의 경우 11=22+22+12+12+12(5개 항)도 가능하다 www.acmicpc.net 0. 시행착오 1. dp[104]로 선언해놓고 for(int i=0~104)로 초기화 -> out of bound... 2. 2중for문 100000 * 100000 으로 해놓고 왜안됨? 뻘짓.. 1. 수학으로 시간복잡도줄이기 문제 : i의 범위 100000 * j의 범위 100000 -> 시초 해결 : i의범위는 root n > n; //dp[i][j] :..

https://www.acmicpc.net/problem/11052 11052번: 카드 구매하기 첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 1,000) 둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1 ≤ Pi ≤ 10,000) www.acmicpc.net 1.dp 관찰방법 i행에 주머니(동전)을 한개씩 !추가! 하면서 target(N개 카드) 를 채워나간다. 2.의사코드 1. i행에 1번째 주머니, 2번째 주머니를 추가해나가면서 관찰한다. 2. 관찰결과 위쪽(이번에 추가된 주머니 미사용하는경우) 과 d[j-i] + arr[i]( j-i개 카드를 추가하기 위해 이번에 추가된 주머니 사용하는경우)를 비교해야함을 알아낸다. 3.전체코드 #include usin..

https://www.acmicpc.net/problem/1912 1912번: 연속합첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다.www.acmicpc.net1 . ox를 그때그때 선택해버리기1.완탐 : i번째수를 선택함, 안함으로 2^n 탐색해야함2. 선택한경우 vs 선택안한경우에서 최적인 경우를 그때그떄 선택한다. 3. 이전값 + 현재값() vs 현재값(나부터 연속합 새로시작)  중에 큰값을 선택하면 된다. 2.전체코드#include using namespace std;long long d[100004], a[100004],n;//d[i]: i자리까지 연속합중 최..

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. 의사코드 1. dp[i]를 정의하고 2. 채워나가면서 규칙(점화식)을 발견하라. 2. 전체코드 #include using namespace std; int n,a[1004],dp[1004]; int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); c..

https://www.acmicpc.net/problem/1520 1520번: 내리막 길 여행을 떠난 세준이는 지도를 하나 구하였다. 이 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 한 칸은 한 지점을 나타내는데 각 칸에는 그 지점의 높이가 쓰여 있으 www.acmicpc.net 1. top-down dp 위에서부터구하는 dp를말한다. 재귀로 구현한다. fibo(15)=fibo(14)+fibo(13) ... 2. bottom-up dp 위에서부터구하는 dp를말한다. 반복문으로 구현한다. fibo(3)=fibo(1)+fibo(2) / fibo(4)= ... / fibo(15)= ... 3. 상하좌우탐색 문제점 -> or 아래 or 5시대각선 탐색은 배열을 i,j 한칸씩 탐색하면서..

https://www.acmicpc.net/problem/1890 1890번: 점프 첫째 줄에 게임 판의 크기 N (4 ≤ N ≤ 100)이 주어진다. 그 다음 N개 줄에는 각 칸에 적혀져 있는 수가 N개씩 주어진다. 칸에 적혀있는 수는 0보다 크거나 같고, 9보다 작거나 같은 정수이며, 가장 www.acmicpc.net 1. 의사코드 1. dp도 배열한칸씩 탐색하는것이다. 2. pass 조건을 잘 생각하면 된다. 3. dp[i][j]= 어쩌구 가 아닌 // d[next] +=d[cur] 형태로도 짤수가 있다. 2.전체코드 #include using namespace std; typedef long long ll; ll dp[104][104],a[104][104]; //오큰수의 갯수 [길이][시작숫자] ..

https://www.acmicpc.net/problem/10844 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 1. 의사코드 1. 규칙발견 && 테이블정의 : dp [길이][끝나는숫자] 의 갯수 아래숫자 == 위행의 좌측 + 위행의 우측 이다. 2. 주의사항 %1억할때, (a%1억 + b%1억) %1억해야 올바른 값이 나온다.. 2. 전체코드 #include using namespace std; typedef long long ll; ll d[104][12]; //오큰수의 갯수 [길이][시작숫자] ll n; int main() { ios::sync_with_stdio(0); cin.tie(0); cin >> n; for..

https://www.acmicpc.net/problem/11057 11057번: 오르막 수 오르막 수는 수의 자리가 오름차순을 이루는 수를 말한다. 이때, 인접한 수가 같아도 오름차순으로 친다. 예를 들어, 2234와 3678, 11119는 오르막 수이지만, 2232, 3676, 91111은 오르막 수가 아니다. 수 www.acmicpc.net 1. 의사코드 1. 아래칸 = 위칸의 총합인것을 발견할수 있다. 2. 전체코드 #include using namespace std; typedef long long ll; int d[1004][10]; //오큰수의 갯수 [길이][시작숫자] int n; int main() { ios::sync_with_stdio(0); cin.tie(0); cin >> n; fi..