알고리즘/백준 (109) 썸네일형 리스트형 [BOJ 11399] ATM 앞에 기다리는 시간은 누적되므로, 누적의 값을 줄여야 총량을 줄일 수 있다. 가장 작은 값들을 먼저 선택해서, 총량을 줄이는 방향으로 코드를 작성한다. 해설코드(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 #include #include #include using namespace std; int N; int answer = 0; int acc = 0; vector v; int main() { cin >> N; for(int i = 1; i > tmp; v.push_back(tmp); } sort(v.begin(), v.end()); for(int i = 0; i [BOJ 1107] 리모컨 0 ~ 500000까지의 채널을 체크하면서, 유효한지를 체크하면 된다. 문자열로 처리하면 시간이 늦어지므로 int로 채널들을 처리하도록 다시 구성했다. 처음에는, 가능성이 있는 채널만 찾아서 체크할려고 했지만 쉽지 않아서 완전 탐색을 했다. 해설코드(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 46 47 48 49 #include #include #include using namespace std; int N, M, tmp; int answer; int arr[6]; bool chk[10]; void func(int.. [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 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.. 이전 1 ··· 4 5 6 7 8 9 10 ··· 14 다음