1부: 재귀

문제 1: 숫자 세기

/*
n=1, 결과 1
n=2, 결과 2 (12, 2)
n=3, 결과 2 (13, 1)
n=4, 결과 4 (14, 13, 24, 124)
n=5, 결과 4 (15, 25, 125, 5)

관찰 결과:
n이 홀수이면 f[n] = f[n-1]
n이 짝수이면 f[n] = f[n-1] + f[n/2]
*/
#include <iostream>

using namespace std;
const int MAX = 10000;
int dp[MAX];

int main() {
    dp[1] = 1;
    int n;
    cin >> n;
    for (int i = 2; i <= n; i++) {
        if (i % 2 == 1) dp[i] = dp[i-1];
        else dp[i] = dp[i-1] + dp[i/2];
    }
    cout << dp[n] << endl;
    return 0;
}

#include <iostream>

using namespace std;
int result = 0;

void recur(int n) {
    result++;
    for (int i = 1; i <= n / 2; i++) recur(i);
}

int main() {
    int n;
    cin >> n;
    recur(n);
    cout << result << endl;
    return 0;
}

문제 2: 숫자 선택

#include <iostream>
#include <cmath>

using namespace std;
const int MAX = 10000;
int arr[MAX];
int ans, n, k;

bool isPrime(int x) {
    if (x < 2) return false;
    for (int i = 2; i * i <= x; i++) {
        if (x % i == 0) return false;
    }
    return true;
}

void dfs(int cnt, int sum, int start) {
    if (cnt == k) {
        if (isPrime(sum)) ans++;
        return;
    }
    for (int i = start; i < n; i++) {
        dfs(cnt + 1, sum + arr[i], i + 1);
    }
}

int main() {
    cin >> n >> k;
    for (int i = 0; i < n; i++) cin >> arr[i];
    dfs(0, 0, 0);
    cout << ans << endl;
    return 0;
}

// 선택/미선택 방식
#include <iostream>
#include <cmath>

using namespace std;
const int MAX = 10000;
int arr[MAX];
int ans, n, k;

bool isPrime(int x) {
    if (x < 2) return false;
    for (int i = 2; i * i <= x; i++) if (x % i == 0) return false;
    return true;
}

void dfs(int idx, int cnt, int sum) {
    if (cnt == k) {
        if (isPrime(sum)) ans++;
        return;
    }
    if (idx >= n) return;
    // 현재 원소 선택 안 함
    dfs(idx + 1, cnt, sum);
    // 현재 원소 선택
    dfs(idx + 1, cnt + 1, sum + arr[idx]);
}

int main() {
    cin >> n >> k;
    for (int i = 0; i < n; i++) cin >> arr[i];
    dfs(0, 0, 0);
    cout << ans << endl;
    return 0;
}

// next_permutation 사용 (중복 문제 발생)
#include <iostream>
#include <cmath>
#include <algorithm>

using namespace std;
const int MAX = 10000;
int arr[MAX];
int ans, n, k;

bool isPrime(int x) {
    if (x < 2) return false;
    for (int i = 2; i * i <= x; i++) if (x % i == 0) return false;
    return true;
}

int main() {
    cin >> n >> k;
    for (int i = 0; i < n; i++) cin >> arr[i];
    
    bool seen[MAX] = {false};
    do {
        int sum = 0;
        for (int i = 0; i < k; i++) sum += arr[i];
        if (isPrime(sum)) seen[sum] = true;
    } while (next_permutation(arr, arr + n));
    
    for (int i = 0; i < MAX; i++) if (seen[i]) ans++;
    cout << ans << endl;
    return 0;
}

// 백트래킹 기반 (방문 체크)
#include <iostream>
#include <cmath>

using namespace std;
const int MAX = 10000;
int arr[MAX];
bool used[MAX];
int ans, n, k;
bool resultCheck[MAX];

bool isPrime(int x) {
    if (x < 2) return false;
    for (int i = 2; i * i <= x; i++) if (x % i == 0) return false;
    return true;
}

void dfs(int cnt, int sum) {
    if (cnt == k) {
        if (isPrime(sum)) resultCheck[sum] = true;
        return;
    }
    for (int i = 0; i < n; i++) {
        if (!used[i]) {
            used[i] = true;
            dfs(cnt + 1, sum + arr[i]);
            used[i] = false;
        }
    }
}

int main() {
    cin >> n >> k;
    for (int i = 0; i < n; i++) cin >> arr[i];
    dfs(0, 0);
    for (int i = 0; i < MAX; i++) if (resultCheck[i]) ans++;
    cout << ans << endl;
    return 0;
}

문제 3: 스키 *

#include <iostream>
#include <algorithm>

using namespace std;
const int N = 1010;
int grid[N][N];
int memo[N][N];
int result = 0;
int n, m;
int dx[] = {-1, 0, 1, 0};
int dy[] = {0, 1, 0, -1};

int dfs(int x, int y) {
    if (memo[x][y]) return memo[x][y];
    memo[x][y] = 1;
    for (int i = 0; i < 4; i++) {
        int nx = x + dx[i], ny = y + dy[i];
        if (nx >= 0 && nx < n && ny >= 0 && ny < m && grid[x][y] > grid[nx][ny]) {
            memo[x][y] = max(memo[x][y], dfs(nx, ny) + 1);
        }
    }
    return memo[x][y];
}

int main() {
    cin >> n >> m;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            cin >> grid[i][j];

    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            result = max(result, dfs(i, j));

    cout << result << endl;
    return 0;
}

2부: 분할 정복

문제 1: 대학 입시 고민

#include <iostream>
#include <algorithm>
#include <cmath>

using namespace std;
const int N = 1000010;
int schools[N], students[N];
long long ans;

int binarySearch(int target, int l, int r) {
    while (l <= r) {
        int mid = (l + r) / 2;
        if (schools[mid] < target) l = mid + 1;
        else r = mid - 1;
    }
    return l;
}

int main() {
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> schools[i];
    sort(schools + 1, schools + n + 1);

    for (int i = 1; i <= m; i++) {
        cin >> students[i];
        int idx = binarySearch(students[i], 1, n);
        int diff = abs(students[i] - schools[idx]);
        if (idx > 1) diff = min(diff, abs(students[i] - schools[idx - 1]));
        ans += diff;
    }
    cout << ans << endl;
    return 0;
}

문제 2: 평면상의 최근접 점쌍

#include <iostream>
#include <cmath>
#include <iomanip>

using namespace std;
const int N = 100000;
int x[N], y[N];

int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) cin >> x[i] >> y[i];

    double minDist = 1e18;
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            long long dx = x[i] - x[j];
            long long dy = y[i] - y[j];
            double dist = sqrt(dx * dx + dy * dy);
            if (dist < minDist) minDist = dist;
        }
    }
    cout << fixed << setprecision(4) << minDist << endl;
    return 0;
}

문제 3: 나무 자르기 *

#include <iostream>
#include <algorithm>

using namespace std;
const int N = 1000010;
long long trees[N];
int n, m;

long long getWood(int height) {
    long long total = 0;
    for (int i = 0; i < n; i++) {
        if (trees[i] > height) total += (trees[i] - height);
    }
    return total;
}

int findHeight(int l, int r, int target) {
    int left = l, right = r;
    while (left <= right) {
        int mid = (left + right) / 2;
        if (getWood(mid) < target) right = mid - 1;
        else left = mid + 1;
    }
    return left - 1;
}

int main() {
    cin >> n >> m;
    for (int i = 0; i < n; i++) cin >> trees[i];
    sort(trees, trees + n);
    int maxTree = trees[n - 1];
    cout << findHeight(0, maxTree, m) << endl;
    return 0;
}

3부: 무차별 대입

문제 1: 완벽한 커플

#include <iostream>

using namespace std;
const int N = 1010;
int boys[N], girls[N];

int main() {
    long long n, m, k;
    cin >> n >> m >> k;
    for (int i = 0; i < n; i++) cin >> boys[i];
    for (int i = 0; i < m; i++) cin >> girls[i];

    long long ans = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (boys[i] + girls[j] == k) ans++;
        }
    }
    cout << ans << endl;
    return 0;
}

문제 2: 간략화

#include <iostream>

using namespace std;
const int N = 1000010;
int arr[N];

bool isSimplest(int a, int b) {
    for (int i = 2; i <= b && i <= a; i++) {
        if (a % i == 0 && b % i == 0) return false;
    }
    return true;
}

int main() {
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < m; i++) cin >> arr[i];

    for (int i = 0; i < m; i++) {
        int cnt = 0;
        for (int j = 1; j < n && j < arr[i]; j++) {
            if (isSimplest(arr[i], j)) cnt++;
        }
        cout << cnt << endl;
    }
    return 0;
}

문제 3: 네 제곱수 정리 *

#include <iostream>

using namespace std;
const int LIMIT = 32768;
bool isSquare[LIMIT + 10];

int main() {
    for (int i = 0; i * i <= LIMIT; i++) isSquare[i * i] = true;

    int t, n;
    cin >> t;
    while (t--) {
        cin >> n;
        int cnt = 0;
        for (int a = 0; a * a < n; a++) {
            for (int b = 0; b * b + a * a < n; b++) {
                for (int c = 0; c * c + b * b + a * a < n; c++) {
                    int d = n - a * a - b * b - c * c;
                    if (!isSquare[d]) continue;
                    if (a * a <= b * b && b * b <= c * c && c * c <= d) {
                        cnt++;
                    }
                }
            }
        }
        cout << cnt << endl;
    }
    return 0;
}

4부: 백트래킹

문제 1: 단어 행렬

#include <iostream>
#include <cstring>

using namespace std;
const int N = 1010;
char grid[N][N];
bool marked[N][N];

int dx[] = {-1, 0, 1, 1, 1, 0, -1, -1};
int dy[] = {1, 1, 1, 0, -1, -1, -1, 0};
string target = "yizhong";
int n;

void searchWord(int x, int y) {
    for (int dir = 0; dir < 8; dir++) {
        bool valid = true;
        for (int step = 1; step < 7; step++) {
            int nx = x + dx[dir] * step;
            int ny = y + dy[dir] * step;
            if (nx < 0 || nx >= n || ny < 0 || ny >= n) {
                valid = false;
                break;
            }
            if (grid[nx][ny] != target[step]) {
                valid = false;
                break;
            }
        }
        if (valid) {
            for (int step = 0; step < 7; step++) {
                int nx = x + dx[dir] * step;
                int ny = y + dy[dir] * step;
                marked[nx][ny] = true;
            }
        }
    }
}

int main() {
    cin >> n;
    memset(grid, '*', sizeof(grid));
    for (int i = 0; i < n; i++) cin >> grid[i];

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (grid[i][j] == 'y') searchWord(i, j);
        }
    }

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (marked[i][j]) cout << grid[i][j];
            else cout << '*';
        }
        cout << endl;
    }
    return 0;
}

문제 2: 도둑 문제

#include <iostream>
#include <algorithm>
#include <climits>

using namespace std;
const int N = 1010;
int values[N];
int minSum = INT_MAX;
int n;

void dfs(int idx, int sum) {
    if (idx == n) return;
    minSum = min(minSum, sum + values[idx]);
    dfs(idx + 1, sum + values[idx]);
}

int main() {
    cin >> n;
    for (int i = 0; i < n; i++) cin >> values[i];

    for (int i = 0; i < n; i++) dfs(i, 0);
    if (n == 0) cout << 0 << endl;
    else cout << minSum << endl;
    return 0;
}

문제 3: 고양이 산 *

#include <iostream>
#include <algorithm>

using namespace std;
const int N = 20;
int catWeight[N];
int carLoad[N];
int n, maxWeight;
int result;

void dfs(int catIdx, int carCnt) {
    if (carCnt >= result) return;
    if (catIdx > n - 1) {
        result = min(result, carCnt);
        return;
    }
    for (int i = 0; i < carCnt; i++) {
        if (carLoad[i] + catWeight[catIdx] <= maxWeight) {
            carLoad[i] += catWeight[catIdx];
            dfs(catIdx + 1, carCnt);
            carLoad[i] -= catWeight[catIdx];
        }
    }
    carLoad[carCnt] = catWeight[catIdx];
    dfs(catIdx + 1, carCnt + 1);
    carLoad[carCnt] = 0;
}

int main() {
    cin >> n >> maxWeight;
    for (int i = 0; i < n; i++) cin >> catWeight[i];
    sort(catWeight, catWeight + n, greater<int>());
    result = n;
    dfs(0, 0);
    cout << result << endl;
    return 0;
}

5부: 탐욕법

문제 1: 타오 타오의 사과 따기 (업그레이드 버전)

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int main() {
    int n, s, a, b;
    cin >> n >> s >> a >> b;
    int maxHeight = a + b;
    vector<pair<int, int>> apples;

    for (int i = 0; i < n; i++) {
        int h, p;
        cin >> h >> p;
        if (h <= maxHeight) apples.push_back({p, h});
    }

    sort(apples.begin(), apples.end());

    int ans = 0;
    for (auto &apple : apples) {
        if (s >= apple.first) {
            s -= apple.first;
            ans++;
        }
    }
    cout << ans << endl;
    return 0;
}

// 계수 정렬 활용
#include <iostream>

using namespace std;
const int MAX_STRENGTH = 110;
int strengthCount[MAX_STRENGTH];

int main() {
    int n, s, a, b;
    cin >> n >> s >> a >> b;
    int maxHeight = a + b;

    for (int i = 0; i < n; i++) {
        int h, p;
        cin >> h >> p;
        if (h <= maxHeight) strengthCount[p]++;
    }

    int ans = 0;
    for (int i = 0; i <= MAX_STRENGTH; i++) {
        while (strengthCount[i] > 0 && s >= i) {
            s -= i;
            ans++;
            strengthCount[i]--;
        }
        if (s < i) break;
    }
    cout << ans << endl;
    return 0;
}

문제 2: 카펫 깔기

#include <iostream>

using namespace std;
const int N = 10010;
int x[N], y[N], w[N], h[N];

int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) cin >> x[i] >> y[i] >> w[i] >> h[i];

    int px, py;
    cin >> px >> py;

    int answer = -1;
    for (int i = n - 1; i >= 0; i--) {
        if (px >= x[i] && px <= x[i] + w[i] && py >= y[i] && py <= y[i] + h[i]) {
            answer = i + 1;
            break;
        }
    }
    cout << answer << endl;
    return 0;
}

문제 3: LAN *

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
const int N = 510;
const int INF = 0x3f3f3f3f;
int graph[N][N];
int dist[N];
bool selected[N];
int n, m;

int prim() {
    memset(dist, 0x3f, sizeof dist);
    int totalWeight = 0;
    for (int i = 0; i < n; i++) {
        int t = -1;
        for (int j = 1; j <= n; j++) {
            if (!selected[j] && (t == -1 || dist[t] > dist[j])) t = j;
        }
        if (i && dist[t] == INF) return INF;
        if (i) totalWeight += dist[t];
        selected[t] = true;
        for (int j = 1; j <= n; j++) dist[j] = min(dist[j], graph[t][j]);
    }
    return totalWeight;
}

int main() {
    memset(graph, 0x3f, sizeof graph);
    cin >> n >> m;
    int sum = 0;
    for (int i = 0; i < m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        graph[u][v] = graph[v][u] = min(graph[u][v], w);
        sum += w;
    }
    int mst = prim();
    cout << sum - mst << endl;
    return 0;
}

6부: 동적 계획법

문제 1: 약초 캐기

#include <iostream>

using namespace std;
const int N = 1010;
int dp[N * 10];

int main() {
    int totalTime, herbCount;
    cin >> totalTime >> herbCount;

    for (int i = 1; i <= herbCount; i++) {
        int time, value;
        cin >> time >> value;
        for (int j = totalTime; j >= time; j--) {
            dp[j] = max(dp[j], dp[j - time] + value);
        }
    }
    cout <> 0) return false;
    return true;
}

int main() {
    cin >> n >> k;
    for (int i = 0; i < n; i++) cin >> vals[i];
    dp[0] = 1;

    for (int i = 0; i < n; i++) {
        for (int j = vals[i]; j <= k; j++) {
            dp[j] += dp[j - vals[i]];
        }
    }
    cout << dp[k] << endl;
    return 0;
}

문제 3: 축하회 *

#include <iostream>

using namespace std;
const int N = 6010;
int dp[N];

int main() {
    int n, m;
    cin >> n >> m;

    for (int i = 0; i < n; i++) {
        int v, w, s;
        cin >> v >> w >> s;
        for (int j = m; j >= 0; j--) {
            for (int k = 0; k * v <= j && k <= s; k++) {
                dp[j] = max(dp[j], dp[j - k * v] + k * w);
            }
        }
    }
    cout << dp[m] << endl;
    return 0;
}