[SISS/C언어 스터디] 25-1학기 3주차 스터디 - 완전 탐색, 추가 과제

[SISS/C언어 스터디] 25-1학기 3주차 스터디 - 완전 탐색, 추가 과제

프로그래머스 풀이 인증 화면 캡쳐

백준 풀이 인증 화면 캡쳐

: 3주차 (3/24~3/30) 프로그래머스 지정 2문제 (완전탐색)

https://school.programmers.co.kr/learn/courses/30/lessons/86491- https://school.programmers.co.kr/learn/courses/30/lessons/87946

 

최소직사각형

---

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

// 명함 크기 배열을 받아 가장 작은 지갑 크기를 계산하는 함수
int solution(int** sizes, size_t sizes_rows, size_t sizes_cols) {
    int max_width = 0, max_height = 0;
    
    for (size_t i = 0; i < sizes_rows; i++) {
        int w = sizes[i][0];
        int h = sizes[i][1];
        
        // 명함을 회전하여 가로가 항상 길도록 정렬
        if (w < h) {
            int temp = w;
            w = h;
            h = temp;
        }
        
        // 최대 가로, 최대 세로 길이 갱신
        if (w > max_width) max_width = w;
        if (h > max_height) max_height = h;
    }
    
    return max_width * max_height;
}

 

피로도

---

#include <stdio.h>
#include <stdbool.h>

int max_dungeons = 0; // 최대 탐험 던전 수

// 백트래킹
void explore(int k, int** dungeons, bool* visited, int count, size_t dungeons_rows) {
    if (count > max_dungeons) { // 현재 탐험한 던전 수가 최댓값보다 클 경우 갱신
        max_dungeons = count;
    }
    
    for (size_t i = 0; i < dungeons_rows; i++) {
        if (!visited[i] && k >= dungeons[i][0]) {  // 미방문 + 최소 피로도 충족 시
            visited[i] = true; // 방문 표시
            explore(k - dungeons[i][1], dungeons, visited, count + 1, dungeons_rows); // 피로도 차감 후 재귀 호출
            visited[i] = false;  // 백트래킹 (방문 해제)
        }
    }
}

// 주어진 피로도(k)로 탐험할 수 있는 최대 던전 수 계산
int solution(int k, int** dungeons, size_t dungeons_rows, size_t dungeons_cols) {
    bool visited[dungeons_rows];
    for (size_t i = 0; i < dungeons_rows; i++) {
        visited[i] = false;
    }
    
    max_dungeons = 0; // 최대 던전 수 초기화
    explore(k, dungeons, visited, 0, dungeons_rows);
    
    return max_dungeons; // 결과 반환
}

 

14889

---

// 14889.c
#include <stdio.h>
#include <stdlib.h>
#include <math.h>

#define INF 1000000000

int N; // 팀원 수
int arr[20][20]; // 능력치 저장 (20x20)
int team[20] = {0}; // 팀 배정
int ans = INF; // 최소 차이 저장

// DFS
void dfs(int pos, int count) {
    if (count == N / 2) { // 팀이 절반씩 나누어졌을 경우
        int start = 0, link = 0;
        for (int i = 0; i < N - 1; i++) {
            for (int j = i + 1; j < N; j++) {
                if (team[i] && team[j]) {
                    start += arr[i][j] + arr[j][i]; // 1
                } else if (!team[i] && !team[j]) {
                    link += arr[i][j] + arr[j][i]; // 0
                }
            }
        }
        int diff = abs(start - link); // 두 팀의 차 계산
        if (diff < ans) ans = diff; // 최소 차이 갱신
        return;
    }
    
    for (int i = pos; i < N; i++) {
        team[i] = 1; // i번째 선수를 1 팀으로
        dfs(i + 1, count + 1); // 다음 선수
        team[i] = 0; // 백트래킹 (원래 상태로)
    }
}

int main() {
    scanf("%d", &N); // N 입력
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            scanf("%d", &arr[i][j]); // 능력치 입력
        }
    }
    
    dfs(0, 0);
    printf("%d\n", ans);
    return 0;
}