연잎의 develog

2579번: 계단 오르기 (acmicpc.net) 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net [문제] [해결전략] 만일 n이 그다지 크지 않았다면, 백트래킹과 같은 방식으로 O(2^N)만에 해결이 가능하지만 지금 처럼 N이 300일때는 어림도 없다 따라서 DP 를 통해 해결해주어야한다. 1. 테이블 정의하기 dp [i] = i번째 계단까지 올라섰을 때 점수 합의 최댓값 만일 위와 같이 테이블을 정의하게 되면 연속한 세계단을 모두 밟을 수 없다는 제약조건을 점화식에 넣을 방법이 없다..! 따라서 테이블을 다른 방식으로..

19575번: Polynomial (acmicpc.net) 19575번: Polynomial 경근이는 수학을 좋아한다. 수학을 너무 좋아하는 나머지 다항식을 빠르게 평가하는 프로그램을 작성했다. 미지수 x로 구성된 다항식 f(x)에서 x에 k를 대입하여 f(k)를 구하는 것을 평가라고 한다 www.acmicpc.net [문제] [해결전략] [풀이] #include #include using namespace std; const int MOD = 1e9 + 7; int solve(int n,int x, vector coef) { long long ans = coef[0] ; for (int i = 1; i > n>> x; vector coef(n+1, 0); int degree; for (int i = 0..

문제집: N과 M (시리즈) (acmicpc.net) 문제집: N과 M (시리즈) www.acmicpc.net 오늘은 N과 M (시리즈 ) 를 통해 순열, 조합, 중복순열, 중복 조합을 연습해보려고 한다! 1. N과 M (1) : 순열 (nPm) 을 구하는 간단한 문제! [풀이] #include #include #include using namespace std; int n, m; int check[9] = { false, }; int pArr[8] = { 0, }; void permutaion(int depth) { if (depth == m) { for (int i = 0; i < m; i++) { cout num[i]; } sort(num, num + n); //오름차순 정렬 permutaion(0..

[C++] 순열(Permutation) 조합(Combination) 알고리즘 :: 개발 블로그 (tistory.com) [C++] 순열(Permutation) 조합(Combination) 알고리즘 백준에서 완전 탐색 문제를 풀다가 항상 조합과 순열을 만들 때 헷갈려서 아예 시간을 내어 정리하였다. 이 네 가지 알고리즘의 뼈대를 이해하면, 여러 방면에 쓰여서 좋은 거 같다. 이후 나오는 hongchan.tistory.com 브루트 포스 문제를 풀다보면 거의 순열 or 조합 의 연장선인 경우가 많다! 오늘은 c++ 로 순열과 조합을 어떤식으로 구현할 수 있는지 정리해보려고 한다. 1) 순열 (nPr) 서로 다른 n개 중 순서를 고려하여 서로 다른 r 개를 뽑는 경우. (순서O, 중복X) 중복을 막기위해 ch..

17626번: Four Squares (acmicpc.net) 17626번: Four Squares 라그랑주는 1770년에 모든 자연수는 넷 혹은 그 이하의 제곱수의 합으로 표현할 수 있다고 증명하였다. 어떤 자연수는 복수의 방법으로 표현된다. 예를 들면, 26은 52과 12의 합이다; 또한 42 + 32 + 1 www.acmicpc.net [문제] 자연수 n이 주어질 때, n을 최소 개수의 제곱수 합으로 표현하는 컴퓨터 프로그램 [해결전략] 1. 재귀탐색 제곱수들을 배열에 저장해놓고, 1 3 9 16 25 36 49 64 재귀함수이용(최대 depth = 4)해서 4개의 정수를 뽑자. 그런데 n의 범위를 살펴보니 1 ≤ n ≤ 50,000 이고 제곱급취하면 225니까 1~ 4개의 정수를 뽑는 경우의수는 ..

1149번: RGB거리 (acmicpc.net) 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net [문제] RGB거리에는 집이 N개 있다. 거리는 선분으로 나타낼 수 있고, 1번 집부터 N번 집이 순서대로 있다. 집은 빨강, 초록, 파랑 중 하나의 색으로 칠해야 한다. 각각의 집을 빨강, 초록, 파랑으로 칠하는 비용이 주어졌을 때, 아래 규칙을 만족하면서 모든 집을 칠하는 비용의 최솟값을 구해보자. 1번 집의 색은 2번 집의 색과 같지 않아야 한다. N번 집의 색은 N-1번 집의 색과 같지..