안 쓰던 블로그

www.acmicpc.net/problem/2133 dp[n] = 3xn 직사각형 채우는 방법의 수 1. n이 홀수면 채울 수 없다 2. n=2면 3가지 방법이 있다 3. n=4면 3x2만큼은 dp[2]에서 했던 값을 사용, 나머지 3x2에 대한 방법이 또 3가지 있다 dp[2]에서 했던 부분을 왼쪽을 잡든 오른쪽을 잡든 같으니까 같은 수로 친다 dp[2]x3=9만큼의 경우의 수가 나온다 그리고 특수 케이스가 있다 이렇게 엇갈리는 방법 두 가지가 있다 dp[4]=dp[2]*3+dp[0]*2 가 된다. dp[4]=11 3. n=6이면 dp[2]+dp[4] 이렇게 볼 수 있지만 둘은 중복되는 모양이 너무 많다 그래서 일단 dp[2]*dp[4]를 해 놓고, 중복 없이 나머지를 넣어야 한다 dp[2]*dp[4]..

www.acmicpc.net/problem/2294 dp배열은 합이 j일 때의 최소 동전 개수를 나타낸다 현재 금액만 사용했을 때 최소 몇 개의 동전이 필요한가 하나씩 보며 전체 dp배열을 업데이트하는 식이다 1원 쓸 때는 1~15원까지 각 개수만큼 사용해서 1,2,3..15까지가 배열에 들어간다 다음 5원 쓸 때는 1~4원까지는 1원을 쓴 그대로 두고, 5원은 5원 1개로 만들 수 있으니까 1이 되고, 6,7,8,9까지는 5+x개의 1원을 쓰니까 각각 2,3,4,5개를 사용해서 만들 수 있다 이 때 이전에 1원 기준으로 계산했던 값에서+5원을 하면 (5원 1개+1원 x개)로 만든 값이 나오니까 j-a[i](1원 x로 만든 값)+1(5원 1개 더한 값)이 식이다. j-a[i]+1 이 값을 현재까지의 최소..

두 수의 합의 모듈러는, 각 수의 모듈러를 더한 모듈러와 같다 즉, 계산 중에 너무 큰 값이 만들어질 것 같고 결과값이 모듈러 연산한 나머지를 출력하는 문제라면, 중간에 연산하면서 바로 모듈러 연산을 해도 최종적으로 같은 결과가 나온다 (합 구하는 문제 같은 경우) (5+4)%2=9%2=1 (5%2)+(4%2)=1+0=1 이런 느낌이다

관련 문제 -이진 검색 트리: www.acmicpc.net/problem/5639 (전위->이진트리) -완전 이진 트리: www.acmicpc.net/problem/9934 (중위->이진트리) 이진 검색 트리 문제부터 본다 전위 순회한 결과 값으로 후위 순회하는 문제이다 전위 순회는 루트-왼쪽-오른쪽 순으로 방문한다 이진 트리는 들어온 값을 루트부터 시작하여 값이 큰지 작은지 비교, 왼쪽/오른쪽 어느 서브 트리로 보낼지를 결정해야 한다 이 문제에서 전위 순회 결과로 이진트리를 만드는 작업은 다음과 같이했다(참고: www.acmicpc.net/problem/1539 ) 1. 전위 순회는 무조건 첫 값이 루트이므로 첫 값은 루트로 넣는다 2. 값을 하나 입력 받는다 3. 현재 노드를 나타낼 now변수를 둔다..

www.acmicpc.net/problem/6603 n개 중에 6개를 뽑는 모든 경우의 수 구하기 몇개를 뽑는지 정해져 있다면 순열을 이용할 수 있다 뽑는 6개에 대해 1이라고 하고, n-6에 대해 0이라고 한 순열을 만들고 모든 순열을 돌면서 1인 경우의 값을 출력한다 #include #include #include using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(NULL); int n; while (1) { cin >> n; vector a(n), d; if (n == 0) break; for (int i = 0; i > a[i]; for (int i = 0; i < n - 6; i++) d.pu..

순열 next_permutation()과 prev_permutation() 직접 구현하기 다음 순열, 이전 순열, 모든 순열 순열 크기 n이 3인 수열을 사전순으로 나열하면 다음과 같다 123 132 213 231 312 321 n=3인 수열은 총 6개가 있다 여기서 먼저 알 수 있는 사실은 크기가 n인 순열을 총 n!개 존재한다는 것이다 첫 번째 오는 수를 n가지 중에서 선택, 그 다음 수를 n-1가지 중에서 선택, 그 다다음 수를 n-2가지 중에서 선택..을 반복하기 때문에 총 가지 수는 n*(n-1)*(n-2)*...*2*1 즉, n!이다 또 알 수 있는 사실은 첫 순열은 오름차순, 마지막 순열은 내림차순이라는 것이다 그러므로 중간 순열을 구하고 싶다면 첫 순열에서 다음, 다음, 다음으로 넘어가서 ..

합이 n이고 길이가 최소 l인 연속된 수열을 구하는 문제 합이 n인 연속된 수열을 $x+(x+1)+(x+2)...(x+L-1)$ 로 두고 x에 대한 식으로 바꾸면 위에 풀이처럼 된다 l이 100까지라고 했으니까 l~100 사이에서 조건에 맞는 x를 찾으면 끝 #include using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); long long n; int l, res = -1, index = 0; cin >> n >> l; for (int i = l; i = 0) { //나눠 떨어지고, 길이가 맞으면 찾음 res = (n - k) / i; index = i; break; } } if (re..