T1 행 우선 탐색

문제 개요

n×m 크기의 격자가 다음 규칙으로 채워져 있습니다:

	열 1	열 2	...	열 m
행 1	1	2	...	m
행 2	m+1	m+2	...	2m
행 3	2m+1	2m+2	...	3m
...	...	...	...	...
행 n	...	...	...	nm

정수 c가 주어지면, c가 위치한 행과 열을 "행 열" 순서로 출력합니다.

핵심 아이디어

격자의 구조를 분석하면 두 가지 핵심 관계를 도출할 수 있습니다:

• 열 계산: c를 m으로 나눈 나머지가 열 번호. 단, 나머지가 0이면 m열에 해당
• 행 계산: c/m의 올림값이 행 번호. 즉, 나머지가 0이면 c/m, 아니면 c/m+1

참고로 입력값 n은 실제 계산에 사용되지 않습니다.

구현

#include <bits/stdc++.h>
using namespace std;

int width, target, row, col;

int main() {
    cin >> width >> width >> target;  // n 무시, 두 번째 width로 덮어쓰기
    
    // 열 계산
    if (target % width == 0) 
        col = width;
    else 
        col = target % width;
    
    // 행 계산
    if (col == width) 
        row = target / width;
    else 
        row = target / width + 1;
    
    cout << row << " " << col << endl;
    return 0;
}

---

T2 변형 피보나치 수열

문제 개요

수열 정의:

• f₁ = 1
• f₂ = a (주어진 상수)
• fᵢ = fᵢ₋₁ + fᵢ₋₂ (i > 2)

주어진 k에 대해 fⱼ ≤ k < fⱼ₊₁을 만족하는 j를 찾습니다.

핵심 아이디어

큰 수 범위(k ≤ 10⁹)를 고려할 때, 단순 재귀는 비효율적입니다. 메모이제이션을 적용하거나, 반복문 기반 bottom-up 방식으로 전환하는 것이 바람직합니다.

구현

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

ll memo[100010];
ll param_a, limit_k;

ll compute(int idx) {
    if (memo[idx] != -1) return memo[idx];
    if (idx == 1) return memo[idx] = 1;
    if (idx == 2) return memo[idx] = param_a;
    return memo[idx] = compute(idx-1) + compute(idx-2);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    memset(memo, -1, sizeof(memo));
    cin >> param_a >> limit_k;
    
    for (int i = 1; i <= 100000; i++) {
        ll current = compute(i);
        ll next = compute(i+1);
        if (current <= limit_k && limit_k < next) {
            cout << i << endl;
            break;
        }
    }
    return 0;
}

---

T3 수직선 여행

문제 개요

수직선 위 n개의 관광지가 주어집니다. 시작점 0에서 출발하여, 한 번에 d 단위씩 좌우로 이동할 수 있습니다. 모든 관광지를 방문할 수 있는 d의 최댓값을 구합니다.

핵심 아이디어

각 관광지 좌표의 절값을 취하면, 문제는 "모든 점에 도달 가능한 최대 보폭"으로 변환됩니다. 이는 모든 좌표의 최대공약수(GCD)를 구하는 문제와 동일합니다.

단일 관광지(n=1) 경우를 처리하기 위해, 가상의 두 번째 값을 추가하는 트릭을 사용할 수 있습니다.

구현

#include <bits/stdc++.h>
#define int long long
using namespace std;

int n;
int spots[100010];
int result;

int get_gcd(int x, int y) {
    return y ? get_gcd(y, x % y) : x;
}

signed main() {
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        cin >> spots[i];
        spots[i] = abs(spots[i]);
    }
    
    // n=1 처리: 자기 자신의 배수로 설정
    spots[n+1] = spots[1] * 2;
    
    result = get_gcd(spots[1], spots[2]);
    for (int i = 3; i <= n; ++i) {
        result = get_gcd(result, spots[i]);
    }
    
    cout << result << endl;
    return 0;
}

---

T4 퍼지 매칭

문제 개요

문자열 S(일부 문자가 '?'로 표시됨)와 패턴 T가 주어집니다. T가 S의 부분열로 매칭될 수 있도록 '?'를 채워, 가능한 모든 결과 중 사전순 최소를 출력합니다.

핵심 아이디어

사전순 최소를 위한 전략:

1. 가능한 매칭 위치 중, 가장 뒤쪽에 T를 배치 (앞쪽 '?'를 'A'로 채울 기회 확보)
2. 매칭 불가 시, 뒤에서부터 탐색하여 '?'가 많은 위치 선택
3. 남은 '?'는 모두 'A'로 채움

구현

#include <bits/stdc++.h>
using namespace std;

string pattern, text;

int main() {
    cin >> pattern >> text;
    
    int p_len = pattern.length();
    int t_len = text.length();
    bool found = false;
    int match_pos = -1;
    
    // 뒤에서부터 매칭 위치 탐색
    for (int i = p_len - t_len; i >= 0; --i) {
        bool valid = true;
        for (int j = 0; j < t_len; ++j) {
            char pc = pattern[i + j];
            char tc = text[j];
            if (pc != '?' && pc != tc) {
                valid = false;
                break;
            }
        }
        if (valid) {
            match_pos = i;
            found = true;
            break;
        }
    }
    
    // 매칭된 위치에 패턴 삽입
    if (found) {
        for (int i = 0; i < t_len; ++i) {
            pattern[match_pos + i] = text[i];
        }
    }
    
    // 남은 '?'를 'A'로 채우고 출력
    for (char c : pattern) {
        cout << (c == '?' ? 'A' : c);
    }
    cout << endl;
    
    return 0;
}

---

T5 순열 순위 변환

문제 개요

다음 규칙으로 정렬된 모든 순열 중 k번째를 찾습니다:

• 길이가 짧은 순열이 먼저 옴
• 길이가 같으면 사전순

예: 1, 1 2, 2 1, 1 2 3, 1 3 2, 2 1 3, ...

핵심 아이디어

길이 n인 순열의 개수는 n!개입니다. 누적 합을 통해 목표 순열의 이를 결정한 후, 팩토리얼 진법(Lehmer code)을 이용해 사전순 위치를 구합니다.

길이 n 순열에서 첫 번째 숫자는 (k-1)/(n-1)! 로 결정되며, 나머지는 재귀적으로 처리합니다.

구현

#include <bits/stdc++.h>
#define int long long
using namespace std;

int target_k;
int factorial_sum = 0;
int prev_fact = 1;
int target_len;
bool used[25];  // 길이 20 정도면 충분 (20! > 10^18)

void solve(int remain_len, int remain_fact, int k) {
    // k번째 사용 가능한 숫자 찾기
    int block_size = remain_fact / remain_len;
    int idx = (k - 1) / block_size + 1;  // 1-based index
    
    int cnt = 0, val = 0;
    for (int i = 1; i <= target_len; ++i) {
        if (!used[i]) {
            ++cnt;
            if (cnt == idx) {
                val = i;
                break;
            }
        }
    }
    
    cout << val;
    if (remain_len > 1) cout << " ";
    
    used[val] = true;
    int next_k = k - (idx - 1) * block_size;
    
    if (remain_len > 1) {
        solve(remain_len - 1, block_size, next_k);
    }
}

signed main() {
    cin >> target_k;
    
    // 길이 결정
    int i = 0;
    while (++i) {
        factorial_sum += prev_fact * i;
        if (factorial_sum >= target_k) {
            target_len = i;
            target_k = target_k - (factorial_sum - prev_fact * i);
            break;
        }
        prev_fact *= i;
    }
    
    solve(target_len, prev_fact * i, target_k);
    return 0;
}