1. 별 찍기 (7)

• 별 찍기 (4)에서, 왼쪽에 있는 별들이 사라지고 공백들이 생겼다
  • 아니면 별 찍기 (5)와 별 찍기 (6)의 조합이라 봐도 될 것 같다
• 다음과 같은 과정을 거치도록 하자.
  • k번째에 별을 배치한 뒤, 현재 배열을 출력한다.
  • 그리고 k번째에 공백을 배치한 뒤, k+1을 호출한다.
    • 단, 현재 k가 n-1이라면 n개까지 다 채운 것이므로 그냥 돌아간다.
  • f(k+1)이 끝났다면, 뒤에 있는 별을 지워야 하므로 k+1번째에 ‘\0’을 배치하낟.
  • 그리고 k번째에 다시 별을 배치한 뒤, 출력한다.

#include <stdio.h>

char s[102];
int n;

void f(int k){
    s[k] = '*';
    puts(s);
    s[k] = ' ';
    if (k == n-1) return;
    f(k+1);
    s[k+1] = '\0';
    s[k] = '*';
    puts(s);
}

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

2. 계단 오르기 7

• 탐색을 할 때, 상태를 다음과 같이 정의하자.
  • n : 현재 계단
  • k : 남은 이동 횟수
  • c : 가장 최근에 이동한 칸 수
• 그래서 이동하고자 하는 거리 1, 2, 3에 대해서, c가 아닐때만 호출하도록 작성하자.

#include <stdio.h>

int t, no[20];
int f(int n, int k, int c)
{
	if (t == n) return 1;
	if (n > t || k == 0) return 0;
	
    int r = 0;

    for (int i=1; i<=3; i++)
        if (i != c) r += f(n+i, k-1, i);
    return r;
}

int main()
{
	int k, b;
	scanf("%d %d %d", &t, &k, &b);

	printf("%d", f(0, k, 0));
}

3. 분할수 출력

• 원본 문제이므로 설명은 생략한다.

#include <stdio.h>
int a[32], cnt;
int min(int a, int b) { return a>b? b:a; }
   
void f(int n, int k) {
    if(n==0) {
        for(int i=0; i<cnt-1; i++)
            printf("%d ", a[i]);
        printf("%d\n", a[cnt-1]);
        return;
    }
    for(int i=min(n, k); i>=1; i--) {
        a[cnt++]=i;
        f(n-i, i);
        cnt--;
    }
}
   
int main() {
    int n, k;
    scanf("%d %d", &n, &k);
    f(n, k);
    return 0;
}

4. 이진복원

• 원본 문제이므로 설명은 생략한다.

#include <stdio.h>
int n, p;
char in[1<<19], out[1<<19];
 
void f(int k, int s) {
    char v=in[p++]; 
    if(v==NULL) return;
    if(v=='-') {
        f(k, s/2);
        f(k+s/2, s/2);
    }
    else
        for(int i=k; i<k+s; i++) 
            out[i]=v;
}
 
int main() {
    scanf("%d %s", &n, in);
    f(0, n);
    printf("%s", out);
}

5. 점프킹 3

• 기본적인 숙직 선생님에서 능력의 개수만 증가했다
• 이것도 못 풀면 안된다

#include <stdio.h>
#include <algorithm>

using namespace std;

int dp[1010101];
int ab[5];

const int inf = 123123123;

int main()
{
    int a, b;
    scanf("%d %d", &a, &b);
    for (int i=0; i<5; i++)
        scanf("%d", &ab[i]);

    for (int i=a+1; i<=b; i++)
    {
        dp[i] = inf;
        for (int j=0; j<5; j++)        
            if (i-ab[j] >= a)
                dp[i] = min(dp[i], dp[i-ab[j]] + 1);
    }

    if (dp[b] != inf) printf("%d", dp[b]);
    else printf("-1");
}