[SISS/C언어 스터디] 겨울학기 8주차 스터디 - 추가 과제

[SISS/C언어 스터디] 겨울학기 8주차 스터디 - 추가 과제

백준 제출 내역 화면 캡쳐

 

11729

---

• 그리디
• 누적 합

#include <stdio.h>
#include <math.h>

// 하노이 탑 이동
// n: 원판의 개수, start: 출발 기둥, to: 도착 기둥, bypass: 경유 기둥
void hanoi(int n, int start, int to, int bypass)
{
    if (n == 1)
    {
        printf("%d %d\n", start, to); // 원판 이동
    }

    else
    {
        // n-1개의 원판을 경유 기둥으로 이동
        hanoi(n - 1, start, bypass, to);
        // 가장 큰 원판을 도착 기둥으로 이동
        printf("%d %d\n", start, to);
        // 경유 기둥에 있는 n-1개의 원판을 도착 기둥으로 이동
        hanoi(n - 1, bypass, to, start);
    }
}

int main()
{
    int num;
    scanf("%d", &num); // 층 수 입력

    printf("%d\n", (int)pow(2, num) - 1); // 이동하는 횟수 계산 및 출력

    hanoi(num, 1, 3, 2); // 하노이 탑 이동을 위한 함수 호출

    return 0;
}

 

21735

---

• 브루트포스
• 백트래킹

#include <stdio.h>
#include <stdlib.h>
#define MAX_N 101

// 최대값 구하는 매크로
#define max(a, b) ((a) > (b) ? (a) : (b))

int snow[MAX_N]; // 눈덩이의 크기
int N, M;        // N: 눈덩이 개수, M: 눈덩이 조작 횟수
int answer = 0;  // 최대 크기의 눈덩이

// 눈덩이를 굴리거나 던짐
void func(int time, int size, int pos)
{
    if (time == M || pos >= N)
    {
        // N에 도달하거나 배열을 벗어난 경우
        answer = max(size, answer); // 최대 눈덩이 크기 갱신

        return;
    }

    for (int i = 1; i <= 2; i++)
    {
        if (i == 1)
        {
            // 눈덩이를 굴리는 경우
            func(time + 1, size + snow[pos + i], pos + i);
        }
        else
        {
            // 눈덩이를 던지는 경우 (크기의 절반)
            func(time + 1, (size / 2) + snow[pos + i], pos + i);
        }
    }
}

int main()
{
    scanf("%d %d", &N, &M); // 눈덩이의 개수와 조작 횟수 입력

    for (int i = 1; i <= N; i++)
    {
        scanf("%d", &snow[i]); // 각 눈덩이의 크기 입력
    }

    func(0, 1, 0);

    printf("%d\n", answer); // 최대 눈덩이 크기 출력

    return 0;
}

 

2239

---

• 구현
• 백트래킹

#include <stdio.h>
#include <stdlib.h>

// 9x9 스도쿠 판, 각 행, 열, 숫자 사용 여부(3x3)
int map[10][10];
int row[10][10] = {0};
int col[10][10] = {0};
int square[10][10] = {0};

// 스도쿠 판 출력
void print()
{
    for (int i = 1; i <= 9; i++)
    {
        for (int j = 1; j <= 9; j++)
        {
            printf("%d", map[i][j]);
        }
        printf("\n");
    }
}

// 스도쿠
void sudoku(int idx)
{
    // 모든 칸을 채웠을 경우 출력 후 종료
    if (idx > 81)
    {
        print();
        exit(0);
    }

    // 현재 인덱스를 행과 열 좌표로
    int x = (idx - 1) / 9 + 1;
    int y = (idx - 1) % 9 + 1;

    // 현재 위치가 속한 3x3 사각형의 번호
    int square_num = (x - 1) / 3 * 3 + (y - 1) / 3 + 1;

    // 현재 칸이 비어있을 경우 가능한 모든 숫자에 대해 시도
    if (map[x][y] == 0)
    {
        for (int i = 1; i <= 9; i++)
        {
            if (row[x][i] == 0 && col[y][i] == 0 && square[square_num][i] == 0)
            {
                // 해당 숫자로 채우고 사용 여부 갱신
                map[x][y] = i;
                row[x][i] = 1;
                col[y][i] = 1;
                square[square_num][i] = 1;

                // 다음 칸으로 이동
                sudoku(idx + 1);

                // 백트래킹(다음 경우를 위해 현재 숫자를 제거 및 사용 여부 업데이트)
                map[x][y] = 0;
                row[x][i] = 0;
                col[y][i] = 0;
                square[square_num][i] = 0;
            }
        }
    }
    else
    {
        // 현재 칸이 채워져 있을 경우 다음 칸으로 이동
        sudoku(idx + 1);
    }
}

int main()
{
    // 입력 및 사용된 숫자 확인
    for (int i = 1; i <= 9; i++)
    {
        for (int j = 1; j <= 9; j++)
        {
            scanf("%1d", &map[i][j]);

            if (map[i][j] != 0)
            {
                row[i][map[i][j]] = 1;
                col[j][map[i][j]] = 1;
                square[((i - 1) / 3) * 3 + (j - 1) / 3 + 1][map[i][j]] = 1;
            }
        }
    }

    sudoku(1);

    return 0;
}