본문 바로가기

분류 전체보기

 (201)
[BOJ 1182] 부분수열의 합(비트마스크, 재귀함수, C++) 이 문제는 비트마스크와 재귀 함수로 풀 수 있다. 비트마스크로 문제를 풀어보았다. 재귀 함수로 풀 경우에는, 함수의 종료 조건을 논리적으로 구성해야 한다. 사실 비트마스크로 문제를 풀기 이전에, 재귀 함수로 문제를 풀었는데 종료조건이 틀렸었다. 합이 S일 때, Return하도록 구성했는데, 인덱스가 N일 때로 구성해야 문제가 없이 답을 구할 수 있다. 1. 비트마스크 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 #include #include using namespace std; int N, S; int arr[21]; int answer = 0; int check[1024*10..
[BOJ 2688] 줄어들지 않아 단계와 끝자리 수를 이용해서 DP를 정의할 수 있다. 단계만을 매개변수로 사용할 경우에는, 점화식을 세울 수 없다. 끝자리 수를 이용해서, 점화식을 완성할 수 있다. DP[i][j] += DP[i - 1][k] (0
[BOJ 2309] 일곱 난쟁이 이 문제는 전체 탐색으로 문제를 해결할 수 있다. 주의해야 할 점은, 100을 만드는 7명의 난쟁이를 찾아야 한다는 것이다. 벡터를 이용해서, 출력문을 손쉽게 해결했다. 해설코드(C++). 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 #include #include #include using namespace std; int tall[10]; vector v; bool flag = true; void func(int idx, int sum){ if(idx == 10){ if(sum == 100 && v.size() == 7){..
[BOJ 1254] 팰린드롬 만들기 이 문제는 다이나믹 프로그래밍으로 꼭 풀어야 하는건 아니다. 문자열의 i ~ j 구간의 팰린드롬 여부를 파악하도록 DP를 구성했다. 문자열의 끝에 0개 이상의 문자를 붙여서, 팰린드롬이 이루어지는지 볼려면, 모든 구간을 보는 것이 아니라, 0 > S; for(int i = 0; i
[BOJ 1562] 계단 수 DP를 이용해서 문제를 풀 때, N만으로는 문제를 해결할 수 없다. 추가적으로 정보가 필요한데, 끝자리 수와 0~9 비트마스크가 필요하다. 끝자리 수를 다음에 올 수 있는 수를 확인하고, 0~9 비트마스크를 조작할 것이다. i = N j = 끝자리의 수 k = 0~9 비트마스크(0 ~ 1023) 위의 정보를 이용해서 점화식을 세우면 된다. 해설코드(C++). 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 #include #include #define mod 1000000000 using namespace std; long long dp[101][10][1024..
[BOJ 1328] 고층 빌딩 N개의 빌딩이 있고 L = A, R = B일 때, N - 1개을 이용해서 어떻게 어떻게 만들 수 있을까? N - 1개의 빌딩들의 범위는 1 ~ N - 1이다. 각 높이에 1을 더해주고, 높이가 1짜리인 빌딩을 놓으면 N개의 빌딩을 만들 수 있다. 높이가 N인 빌딩을 이용했다면, 점화식을 세울 수 있을지 없을지도 모른다. 하지만, 높이가 1짜리인 빌딩을 이용하므로 점화식이 간편해진다. 해설코드(C++). 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 #include using namespace std; int N, L, R; long long dp[101][101][101]; int main() { cin >> N >> L >> R; dp[1][1][..
[BOJ 2618] 경찰차 처음엔 DP를 정의하기 위해서, 5차원 배열(경찰차 1, 2의 위치 + 현재 해결중인 사건)을 생각했었는데, 1000^5는 메모리제한을 초과하게 된다. 5차원 배열의 크기를 줄이는 것을 생각해보면, 경찰차 1, 2이 해결한 마지막 사건들을 이용하면 된다. 왜냐하면, 같은 사건은 중복된 장소에서 발생하지 않으므로, 마지막 사건들은 즉, 현재 해결중인 사건을 표현하고 경찰차의 위치도 나타낼 수 있다. 전체 탐색을 통해서 DP 배열을 완성하고, 한 단계씩 최소값을 찾아가면서 값을 출력하면 된다. 해설코드(C++). 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40..
[BOJ 1256] 사전 이 문제는, 조합에 대한 고등학교 공식을 알아야 풀 수 있다. C(N, M) = C(N - 1, M - 1) + C(N - 1, M) 이 식으로, K의 범위를 체크할 수 있다. 하지만, 단어를 찾기 위해서는 하나 더 생각할 필요가 있다. 1) a _ _ _ _ 2) z _ _ _ _ 위와 같은 형태가 있을 때, K와 대소관계에 따라서 1), 2) 중 하나가 선택된다. 만약 N이 2, M이 3이라고 하면, 1)이 되려면 K > N >> M >>K; C[0][0] = 1; for(int i = 1; i

티스토리툴바