PS/BOJ
BOJ 9095 1, 2, 3 더하기
boj 9095 1, 2, 3 더하기 D[i] = 정수 i를 1, 2, 3의 합으로 나타내는 방법의 수라고 하자. 앞 부분은 겹치는 부분이므로 맨 마지막에 올 수 있는 1, 2, 3의 경우만 살펴보면 된다. n = n-1 + 1 -> n-1을 1, 2, 3 합으로 만드는 방법들을 나열하고 각 끝에 1을 붙이는 경우 n = n-2 + 2 -> n-2를 1, 2, 3 합으로 만드는 방법들을 나열하고 각 끝에 2를 붙이는 경우 n = n-3 + 3 -> n-3을 1, 2, 3 합으로 만드는 방법들을 나열하고 각 끝에 3을 붙이는 경우 D[i]는 위 세 가지 경우의 합이다. 그러므로 점화식을 D[i] = D[i-1] + D[i-2] + D[i-3]로 설정하고 구현한다. #include using namespac..
BOJ 11727 2xN 타일링 2
boj 11727 2xN 타일링 2 boj 11726 2xN 타일링 문제에서 2x2 타일이 추가된 경우이다. 똑같은 방식으로 테이블 D[i] = 1x2, 2x1, 2x2 타일로 채우는 경우의 수 라고 정의한다. 이 때, 다른 점은 끝에 2칸을 채우는 방법이 2x1 타일 2개를 이용하는 방법과 2x2 타일을 이용하는 방법으로 2가지이다. 그러므로 점화식으로D[i] = D[i-1] + 2xD[i-2] 를 설정하고 구현한다. #include using namespace std; int n; int D[1005]; int main(void) { ios_base::sync_with_stdio(0); cin.tie(0); cin >> n; D[1] = 1; D[2] = 3; for (int i = 3; i
BOJ 11726 2xN 타일링
boj 11726 2xN 타일링 간단한 DP 문제이다. DP가 무엇인지를 다시 생각해보면, 하위 문제들을 먼저 푼 후 그것들을 쌓아올려 주어진 문제를 해결하는 알고리즘이다. DP 문제를 풀 때 중점은 테이블을 정의해주고, 그 테이블의 제일 하위 값들이 무엇일까를 생각하며 점화식을 찾는 것이다. 먼저 테이블 설정을 해보면, D[i] = 1x2, 2x1 타일로 채우는 경우의 수 라고 정의하자. 전체 경우의 수 D[i]는 아래 그림과 같이 맨 끝의 한 칸을 1x2 타일이 채우는 경우와 맨 끝의 두 칸을 2x1 타일 2개가 채우는 경우 2가지로 나뉜다. 맨 끝이 3칸이 남는 경우는 더 채우면 결국 앞의 2가지와 겹치기 때문에 생각할 필요가 없다. 그러므로 점화식을 D[i] = D[i-1] + D[i-2]로 설정..
BOJ 1920 수 찾기
boj 1920 수 찾기 예시로 A 배열에 '3 5 6 9 10 12 14 26 35 41' 이 주어졌다고 하고, 14가 있는지 알아본다고 하자. 입력 받은 후에 sort 함수를 이용해서 정렬하면 앞과 같이 정렬된 상태일 것이다. 원래 문제는 A 안에 14가 있는지만 확인하면 되지만, 14가 A 안에서 위치하는 인덱스를 반환하는 함수를 구현해보려고 한다. st와 en은 14가 있을 수 있는 범위의 처음과 끝 인덱스를 의미한다. mid는 (st+en)/2 이다. A[mid]와 14의 값을 비교하며 st와 en의 값을 계속 바꿔나갈 것이다. 만약 A[mid] > 14 이면, 14는 mid와 en 사이에 있음이 자명하고, 그러므로 st = mid+1 이라고 할 수 있다. 만약 A[mid] < 1..
BOJ 6603 로또
boj 6603 로또 숫자를 입력 받아 지정하고 그 갯수의 숫자 중 가능한 6개 조합을 모두 출력해야하는 문제이다. 백트레킹 기법을 이용하여 문제를 해결했다. #include #include using namespace std; int k; vector s; vector l; void func(int num) { if (s.size() == 6) { for (int i = 0; i l[i]; func(0); cout