[23년 동계 스터디] 코딩 테스트 기출 풀이 6주차

1. 스타트와 링크 - C++

 

#include<iostream>
#include<math.h>
using namespace std;

int stats[21][21];
bool check[22];
int N;
int ans = 1000000000; // 10억

void DFS(int x, int pos) // x는 카운트 수, pos는 다음 값
{
    if (x == N / 2) // 카운트수가 정원의 1/2이 됐을 때 능력치합 계산
    {
        int start, link;
        start = 0;
        link = 0;

        for (int i = 1; i <= N; i++)
       {
            for (int j = 1; j <= N; j++)
               {
                if (check[i] == true && check[j] == true) start += stats[i][j];
                if (check[i] == false && check[j] == false) link += stats[i][j];
                }
        }       

        int temp = abs(start - link);
        if (ans > temp) ans = temp;
        return;
     }

    for (int i = pos; i < N; i++)
    {
        check[i] = true;
        DFS(x + 1, i + 1);
        check[i] = false;
     }
}

int main()
{
    cin >> N;
    for (int i = 1; i <= N; i++)
    {
        for (int j = 1; j <= N; j++)
            {
                 cin >> stats[i][j];
             }
    }
    DFS(0, 1); // 카운트 0회부터 숫자는 1부터 시작

    cout << ans;
}

 

-----------------------------------------------------------------------------------------

 

2. 경사로 - C++

 

#include<iostream>
#include<cmath>
 
#define endl "\n"
#define MAX 100
using namespace std;
 
int N, L;
int MAP[MAX][MAX];
int MAP2[MAX][MAX];
 
void Input()
{
    cin >> N >> L;
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            cin >> MAP[i][j];
            MAP2[j][i] = MAP[i][j];
        }
    }
}
 
bool Can_Make_Road(int A[][MAX], int x, int y)
{
    int Standard = A[x][y + 1];
    for (int j = y + 1; j < y + 1 + L; j++)
    {
        if (A[x][j] != Standard) return false;
    }
    return true;
}
 
int Make_Road(int A[][MAX])
{
    int Total_Road = 0;
    for (int i = 0; i < N; i++)
    {
        bool Can_Road = true;
        int Before_Road = 1;
 
        for (int j = 0; j < N - 1; j++)
        {
            if (A[i][j] == A[i][j + 1]) Before_Road++;    // 1번 Case
            else if (A[i][j] == A[i][j + 1] + 1)        // 2번 Case 앞에것이 더 높을 때
            {
                if (Can_Make_Road(A, i, j) == true)
                {
                    j = j + L - 1;
                    Before_Road = 0;
                }
                else
                {
                    Can_Road = false;
                    break;
                }
            }
            else if (A[i][j] + 1 == A[i][j + 1])        // 3번 Case 뒤에것이 더 높을 때
            {
                if (Before_Road >= L)
                {
                    Before_Road = 1;
                }
                else
                {
                    Can_Road = false;
                    break;
                }
            }
            else if (abs(A[i][j] - A[i][j + 1]) >= 2)
            {
                Can_Road = false;
                break;
            }
        }
 
        if (Can_Road == true)
        {
            Total_Road++;
        }
    }
    return Total_Road;
}
 
void Solution()
{
    int A = Make_Road(MAP);
    int B = Make_Road(MAP2);
 
    cout << A + B << endl;
}
 
void Solve()
{
    Input();
    Solution();
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}