1번

계단오르기,숏다리 계단, 찬스 등 숙지하자. 원리는 같다. 필요한 상태가 있으면 함수에
추가해서 해결하면 된다.

f(n, k) = n칸을 정확히 k번 이동해서 올라가는 방법의 수

#include <stdio.h>

int f(int n, int k) {
    if (k == 0) return n == 0 ? 1 : 0;   // 이동을 다 썼으면 딱 도착했을 때만 1
    if (n <= 0) return 0;                // 이동이 남았는데 더 갈 칸이 없음
    return f(n - 1, k - 1) + f(n - 2, k - 1) + f(n - 3, k - 1);
}

int main() {
    int n, k;
    scanf("%d %d", &n, &k);
    printf("%d\n", f(n, k));
}

2번

광석수집 문제에서 방향하나 추가하면 된다.

#include <stdio.h>

#define EMPTY -1000000000   // 아직 안 구했다는 표시 (실제 합으로는 절대 나올 수 없는 값)

int n, m;
int A[1001][1001];
int memo[1001][1001];      // (r, c)에서 도착 칸까지의 최대 합

int max(int a, int b) { return a > b ? a : b; }

int f(int r, int c) {
    if (r > n || c > m) return EMPTY;            // 격자 밖: 절대 고르지 않게 아주 작은 값
    if (r == n && c == m) return A[r][c];        // 도착 칸
    if (memo[r][c] != EMPTY) return memo[r][c];  // 이미 구한 값

    int best = max(f(r, c + 1), max(f(r + 1, c), f(r + 1, c + 1)));  
    memo[r][c] = A[r][c] + best;
    return memo[r][c];
}

int main() {
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++) {
            scanf("%d", &A[i][j]);
            memo[i][j] = EMPTY;                  // 처음엔 전부 안 구했다고 표시
        }
    printf("%d\n", f(1, 1));
    return 0;
}

3번

다이아몬드출력, 모래시계출력같은거는 관계기반으로 출제하기가 어려우니까
출제가 되더라도 그냥 단순 재귀함수 여러개로 풀게할 가능성이 높다.

if(k==0) return;
f(k-1);
s[k]='*';
s[k-1]=' ';
puts(s+1);       

4번

#include <stdio.h>

int n;
int A[128][128];
int mx[129];   // mx[size]: 한 변이 size인 영역들의 가치 중 최댓값 (size = 1, 2, 4, ..., n만 사용)

int f(int r, int c, int size) {
    int sum=0;
    if (size == 1) {
        sum = A[r][c];                     // 한 칸짜리 
    } else {
        int h = size / 2;                  
        sum = f(r, c, h)                   
            + f(r, c + h, h)               
            + f(r + h, c, h)               
            + f(r + h, c + h, h);         
    }
    if (sum > mx[size]) mx[size] = sum;    // 이 크기의 최댓값 갱신
    return sum;
}

int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            scanf("%d", &A[i][j]);

    for (int s = 1; s <= n; s *= 2) mx[s] = -2000000000;   // 음수도 나오니까 아주 작은 값으로 시작

    f(0, 0, n);

    for (int s = 1; s <= n; s *= 2) printf("%d\n", mx[s]);
}

5번

은근 어렵다

#include <stdio.h>

int K;
int cnt, ans[31];  

int min(int a, int b) { return a > b ? b : a; }

void f(int n, int lo) {
    if (n == 0) {                          
        printf("%d", ans[0]);
        for (int i = 1; i < cnt; i++) printf(" %d", ans[i]);
        printf("\n");
        return;
    }
    for (int i = lo; i <= min(n, K); i++) {   // 직전 수 이상만 골라서 오름차순 유지
        ans[cnt++] = i;
        f(n - i, i);
        cnt--;
    }
}

int main() {
    int n;
    scanf("%d %d", &n, &K);
    f(n, 1);
    return 0;
}

6번

#include<stdio.h>

void f(int n,int k){
	if(n==0) return;
	f(n/k,k);
	if(n%k<10) printf("%d",n%k);
	else printf("%c",n%k+'A'-10);
}
int main(){
	int n,k;
	scanf("%d%d",&n,&k);
	if(n==0) printf("0");
	else f(n,k);
}