Bin_S+StudyRoom

• 문제

한수는 캠프를 마치고 집에 돌아가려 한다. 한수는 현재 왼쪽 아래점에 있고 집은 오른쪽 위에 있다. 그리고 한수는 집에 돌아가는 방법이 다양하다. 단, 한수는 똑똑하여 한번 지나친 곳을 다시 방문하지는 않는다.

      cdef  ...f  ..ef  ..gh  cdeh  cdej  ...f 
      bT..  .T.e  .Td.  .Tfe  bTfg  bTfi  .Tde 
      a...  abcd  abc.  abcd  a...  a.gh  abc. 
거리 :  6     6     6     8     8    10    6

위 예제는 한수가 집에 돌아갈 수 있는 모든 경우를 나타낸 것이다. T로 표시된 부분은 가지 못하는 부분이다. 문제는 R x C 맵에 못가는 부분이 주어지고 거리 K가 주어지면 한수가 집까지도 도착하는 경우 중 거리가 K인 가짓수를 구하는 것이다.

• 입력

첫 줄에 정수 R(1 ≤ R ≤ 5), C(1 ≤ C ≤ 5), K(1 ≤ K ≤ R×C)가 공백으로 구분되어 주어진다. 두 번째부터 R+1번째 줄까지는 R×C 맵의 정보를 나타내는 '.'과 'T'로 구성된 길이가 C인 문자열이 주어진다.

• 출력

첫 줄에 거리가 K인 가짓수를 출력한다.

• 예제 입력

3 4 6
....
.T..
....

• 예제 출력

4

• 접근방식

방문한 곳은 다시 방문하지 않으면 visited 필요, 경우의 수를 구하는 문제여서 재귀하면서 원복 필요

• 코드

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

const int dy[4] = { -1, 0 , 1,0 };
const int dx[4] = { 0 , 1 , 0 ,-1 };
int r, c, k, visited[14][14];
char _map[14][14];
string s;

int funtion(int y, int x)
{
    if (y == 0 && x == c - 1)
    {
        if (k == visited[y][x])   return 1;
        return 0;
    }
    int result = 0;
    for (int i = 0; i < 4; i++)
    {
        int ny = y + dy[i];
        int nx = x + dx[i];
        if (ny < 0 || nx < 0 || ny >= r || nx >= c || visited[ny][nx] || _map[ny][nx] == 'T')   continue;
        visited[ny][nx] = visited[y][x] + 1;
        result += funtion(ny, nx);
        visited[ny][nx] = 0;
    }
    return result;
}

int main()
{
    cin >> r >> c >> k;
    for (int i = 0; i < r; i++)
    {
        cin >> s;
        for (int j = 0; j < c; j++)
        {
            _map[i][j] = s[j];
        }
    }
    visited[r - 1][0] = 1;
    cout << funtion(r - 1, 0);
    return 0;
}

• 문제링크 : https://www.acmicpc.net/problem/1189

• 문제

2017년 4월 5일 식목일을 맞이한 진아는 나무를 심는 대신 하이테크관 앞 화단에 꽃을 심어 등교할 때 마다 꽃길을 걷고 싶었다.

진아가 가진 꽃의 씨앗은 꽃을 심고나면 정확히 1년후에 꽃이 피므로 진아는 다음해 식목일 부터 꽃길을 걸을 수 있다.

하지만 진아에게는 꽃의 씨앗이 세개밖에 없었으므로 세 개의 꽃이 하나도 죽지 않고 1년후에 꽃잎이 만개하길 원한다.

꽃밭은 N*N의 격자 모양이고 진아는 씨앗을 (1,1)~(N,N)의 지점 중 한곳에 심을 수 있다. 꽃의 씨앗은 그림 (a)처럼 심어지며 1년 후 꽃이 피면 그림 (b)모양이 된다.

꽃을 심을 때는 주의할 점이있다. 어떤 씨앗이 꽃이 핀 뒤 다른 꽃잎(혹은 꽃술)과 닿게 될 경우 두 꽃 모두 죽어버린다. 또 화단 밖으로 꽃잎이 나가게 된다면 그 꽃은 죽어버리고 만다.

그림(c)는 세 꽃이 정상적으로 핀 모양이고 그림(d)는 두 꽃이 죽어버린 모양이다.

하이테크 앞 화단의 대여 가격은 격자의 한 점마다 다르기 때문에 진아는 서로 다른 세 씨앗을 모두 꽃이 피게하면서 가장 싼 가격에 화단을 대여하고 싶다.

단 화단을 대여할 때는 꽃잎이 핀 모양을 기준으로 대여를 해야하므로 꽃 하나당 5평의 땅을 대여해야만 한다.

돈이 많지 않은 진아를 위하여 진아가 꽃을 심기 위해 필요한 최소비용을 구해주자!

• 입력

입력의 첫째 줄에 화단의 한 변의 길이 N(6≤N≤10)이 들어온다.

이후 N개의 줄에 N개씩 화단의 지점당 가격(0≤G≤200)이 주어진다.

• 출력

꽃을 심기 위한 최소 비용을 출력한다.

• 예제 입력

6
1 0 2 3 3 4
1 1 1 1 1 1
0 0 1 1 1 1
3 9 9 0 1 99
9 11 3 1 0 3
12 3 0 0 0 1

• 예제 출력

12

• 접근방식

3개만 심으면 돼서 완전 탐색으로 접근했다. 꽃을 심으면 방문한 위치와 상 하 좌 우로 총 5개를 방문처리 하면된다.

• 코드

#include <iostream>
#include <algorithm>

using namespace std;

const int dy[4] = { -1, 0 , 1,0 };
const int dx[4] = { 0 , 1 , 0 ,-1 };
int n, visited[24][24], p[24][24], result = 999999;

int setflower(int y, int x)
{
    visited[y][x] = 1;
    int sum = p[y][x];
    for (int i = 0; i < 4; i++)
    {
        int ny = y + dy[i];
        int nx = x + dx[i];
        visited[ny][nx] = 1;
        sum += p[ny][nx];
    }
    return sum;
}

void eraseflower(int y, int x)
{
    visited[y][x] = 0;
    for (int i = 0; i < 4; i++)
    {
        int ny = y + dy[i];
        int nx = x + dx[i];
        visited[ny][nx] = 0;
    }
}

bool check(int y, int x)
{
    if (visited[y][x])   return false;
    for (int i = 0; i < 4; i++)
    {
        int ny = y + dy[i];
        int nx = x + dx[i];
        if (ny < 0 || ny >= n || nx < 0 || nx >= n || visited[ny][nx])
        {
            return false;
        }
    }
    return true;
}


void flower(int cnt, int hap)
{
    if (cnt == 3)
    {
        result = min(result, hap);
        return;
    }
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            if (check(i, j))
            {
                flower(cnt + 1, hap + setflower(i, j));
                eraseflower(i, j);
            }
        }
    }
}

int main()
{
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            cin >> p[i][j];
        }
    }
    flower(0, 0);
    cout << result;
    return 0;
}

• 문제링크 : https://www.acmicpc.net/problem/14620

• 문제

사다리 게임은 N개의 세로선과 M개의 가로선으로 이루어져 있다. 인접한 세로선 사이에는 가로선을 놓을 수 있는데, 각각의 세로선마다 가로선을 놓을 수 있는 위치의 개수는 H이고, 모든 세로선이 같은 위치를 갖는다. 아래 그림은 N = 5, H = 6 인 경우의 그림이고, 가로선은 없다.

초록선은 세로선을 나타내고, 초록선과 점선이 교차하는 점은 가로선을 놓을 수 있는 점이다. 가로선은 인접한 두 세로선을 연결해야 한다. 단, 두 가로선이 연속하거나 서로 접하면 안 된다. 또, 가로선은 점선 위에 있어야 한다.

위의 그림에는 가로선이 총 5개 있다. 가로선은 위의 그림과 같이 인접한 두 세로선을 연결해야 하고, 가로선을 놓을 수 있는 위치를 연결해야 한다.

사다리 게임은 각각의 세로선마다 게임을 진행하고, 세로선의 가장 위에서부터 아래 방향으로 내려가야 한다. 이때, 가로선을 만나면 가로선을 이용해 옆 세로선으로 이동한 다음, 이동한 세로선에서 아래 방향으로 이동해야 한다.

위의 그림에서 1번은 3번으로, 2번은 2번으로, 3번은 5번으로, 4번은 1번으로, 5번은 4번으로 도착하게 된다. 아래 두 그림은 1번과 2번이 어떻게 이동했는지 나타내는 그림이다.

1번 세로선	2번 세로선

사다리에 가로선을 추가해서, 사다리 게임의 결과를 조작하려고 한다. 이때, i번 세로선의 결과가 i번이 나와야 한다. 그렇게 하기 위해서 추가해야 하는 가로선 개수의 최솟값을 구하는 프로그램을 작성하시오.

• 입력

첫째 줄에 세로선의 개수 N, 가로선의 개수 M, 세로선마다 가로선을 놓을 수 있는 위치의 개수 H가 주어진다. (2 ≤ N ≤ 10, 1 ≤ H ≤ 30, 0 ≤ M ≤ (N-1)×H)

둘째 줄부터 M개의 줄에는 가로선의 정보가 한 줄에 하나씩 주어진다.

가로선의 정보는 두 정수 a과 b로 나타낸다. (1 ≤ a ≤ H, 1 ≤ b ≤ N-1) b번 세로선과 b+1번 세로선을 a번 점선 위치에서 연결했다는 의미이다.

가장 위에 있는 점선의 번호는 1번이고, 아래로 내려갈 때마다 1이 증가한다. 세로선은 가장 왼쪽에 있는 것의 번호가 1번이고, 오른쪽으로 갈 때마다 1이 증가한다.

입력으로 주어지는 가로선이 서로 연속하는 경우는 없다.

• 출력

i번 세로선의 결과가 i번이 나오도록 사다리 게임을 조작하려면, 추가해야 하는 가로선 개수의 최솟값을 출력한다. 만약, 정답이 3보다 큰 값이면 -1을 출력한다. 또, 불가능한 경우에도 -1을 출력한다.

• 예제 입력

2 0 3

2 1 3
1 1

5 5 6
1 1
3 2
2 3
5 1
5 4

6 5 6
1 1
3 2
1 3
2 5
5 5

5 8 6
1 1
2 2
3 3
4 4
3 1
4 2
5 3
6 4

5 12 6
1 1
1 3
2 2
2 4
3 1
3 3
4 2
4 4
5 1
5 3
6 2
6 4

5 6 6
1 1
3 1
5 2
4 3
2 3
1 4

• 예제 출력

0

1

3

3

-1

-1

2

• 접근방식

범위가 2<=N<=10, 1<=H<=30 이고 추가 되는 가로선의 개수가 3개가 넘으면 안되기 때문에 300C3이 최대값이다.

상태값을 저장하는 visited 필요, i번째 세로선의 결과가 i번인지 체크하는 함수 필요

• 코드

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int n, m, h, a, b, visited[34][34], result = 9999999;

bool itoi_check()
{
    for (int i = 1; i <= n; i++)
    {
        int start = i;
        for (int j = 1; j <= h; j++)
        {
            if (visited[j][start])  start++; //선을 오른쪽에 존재
            else if (visited[j][start - 1]) start--; // 선을 왼쪽에 존재
        }
        if (start != i) return false;
    }
    return true;
}

void line(int here, int cnt)
{
    if (cnt > 3 || cnt >= result)    return;
    if (itoi_check())
    {
        result = min(result, cnt);
        return;
    }

    for (int i = here; i <= h; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            if (visited[i][j] || visited[i][j - 1] || visited[i][j + 1])   continue; // 선을 그려야 하는 부분에 선이 존재하면 그리지 않음
            visited[i][j] = 1;
            line(i, cnt + 1);
            visited[i][j] = 0;
        }

    }
}

int main()
{
    cin >> n >> m >> h;

    for (int i = 0; i < m; i++)
    {
        cin >> a >> b;
        visited[a][b] = 1;
    }

    line(1, 0);
    cout << ((result == 9999999) ? -1 : result);

    return 0;
}

• 문제링크 : https://www.acmicpc.net/problem/15684

• 문제

상근이는 슬로베니아의 도시 Donji Andrijevci를 여행하고 있다. 이 도시의 도로는 깊이가 K인 완전 이진 트리를 이루고 있다. 깊이가 K인 완전 이진 트리는 총 2K-1개의 노드로 이루어져 있다. (아래 그림) 각 노드에는 그 곳에 위치한 빌딩의 번호가 붙여져 있다. 또, 가장 마지막 레벨을 제외한 모든 집은 왼쪽 자식과 오른쪽 자식을 갖는다.

상근이는 도시에 있는 모든 빌딩에 들어갔고, 들어간 순서대로 번호를 종이에 적어 놓았다. 한국으로 돌아온 상근이는 도시가 어떻게 생겼는지 그림을 그려보려고 하였으나, 정확하게 기억이 나지 않아 실패했다. 하지만, 어떤 순서로 도시를 방문했는지 기억해냈다.

1. 가장 처음에 상근이는 트리의 루트에 있는 빌딩 앞에 서있다.
2. 현재 빌딩의 왼쪽 자식에 있는 빌딩에 아직 들어가지 않았다면, 왼쪽 자식으로 이동한다.
3. 현재 있는 노드가 왼쪽 자식을 가지고 있지 않거나 왼쪽 자식에 있는 빌딩을 이미 들어갔다면, 현재 노드에 있는 빌딩을 들어가고 종이에 번호를 적는다.
4. 현재 빌딩을 이미 들어갔다 온 상태이고, 오른쪽 자식을 가지고 있는 경우에는 오른쪽 자식으로 이동한다.
5. 현재 빌딩과 왼쪽, 오른쪽 자식에 있는 빌딩을 모두 방문했다면, 부모 노드로 이동한다.

왼쪽 그림에 나와있는 마을이라면, 상근이는 2-1-3 순서대로 빌딩을 들어갔을 것이고, 오른쪽 그림의 경우에는 1-6-4-3-5-2-7 순서로 들어갔을 것이다. 상근이가 종이에 적은 순서가 모두 주어졌을 때, 각 레벨에 있는 빌딩의 번호를 구하는 프로그램을 작성하시오.

• 입력

첫째 줄에 K (1 ≤ K ≤ 10)가 주어진다.

둘째 줄에는 상근이가 방문한 빌딩의 번호가 들어간 순서대로 주어진다. 모든 빌딩의 번호는 중복되지 않으며, 구간 [1,2^K)에 포함된다.

• 출력

총 K개의 줄에 걸쳐서 정답을 출력한다. i번째 줄에는 레벨이 i인 빌딩의 번호를 출력한다. 출력은 왼쪽에서부터 오른쪽 순서대로 출력한다.

• 예제 입력

2
2 1 3

3
1 6 4 3 5 2 7

• 예제 출력

1
2 3

3
6 2
1 4 5 7

• 접근방식

완전 이진 트리 탐색에서 InOrder로 탐색하는걸 Level화 한 문제이다.

주어진 배열 {1,6,4,3,5,2,7} 에서 중앙은 3이고 나눠진 배열 {1,6,4} , {5,2,7}에서 중앙은 6, 2 이고 나머지는 1,4,5,7 이다.
즉, 중앙에 있는 값을 맨 위로 (level 1) 그 다음 배열에서 중앙에 있는 값을 위로 (level 2) 나눠져 있는 배열의 갯수가 2개 이하일때 (탐색의 시작과 끝이 같은 index) 일 때 재귀를 멈추는 기저사례로 등록하면 된다.

• 코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>

using namespace std;

int n, a[1024];
vector<int> result[14];

void half(int start, int end, int level)
{
    if (start > end)   return;
    if (start == end) // 기저 사례
    {
        result[level].push_back(a[start]);
        return;
    }

    int mid = (start + end) / 2;
    result[level].push_back(a[mid]);
    half(start, mid - 1, level + 1);
    half(mid + 1, end, level + 1);
    return;
}

int main()
{
    cin >> n;

    int end = (int)pow(2, n) - 1;

    for (int i = 0; i < end; i++)
    {
        cin >> a[i];
    }

    half(0, end, 1);

    for (int i = 1; i <= n; i++)
    {
        for (int j : result[i])
        {
            cout << j << " ";
        }
        cout << endl;
    }

    return 0;
}

• 문제링크 : https://www.acmicpc.net/problem/9934

• 문제

두 종류의 부등호 기호 ‘<’와 ‘>’가 k개 나열된 순서열 A가 있다. 우리는 이 부등호 기호 앞뒤에 서로 다른 한 자릿수 숫자를 넣어서 모든 부등호 관계를 만족시키려고 한다. 예를 들어, 제시된 부등호 순서열 A가 다음과 같다고 하자. 

A ⇒ < < < > < < > < >

부등호 기호 앞뒤에 넣을 수 있는 숫자는 0부터 9까지의 정수이며 선택된 숫자는 모두 달라야 한다. 아래는 부등호 순서열 A를 만족시키는 한 예이다. 

3 < 4 < 5 < 6 > 1 < 2 < 8 > 7 < 9 > 0

이 상황에서 부등호 기호를 제거한 뒤, 숫자를 모두 붙이면 하나의 수를 만들 수 있는데 이 수를 주어진 부등호 관계를 만족시키는 정수라고 한다. 그런데 주어진 부등호 관계를 만족하는 정수는 하나 이상 존재한다. 예를 들어 3456128790 뿐만 아니라 5689023174도 아래와 같이 부등호 관계 A를 만족시킨다. 

5 < 6 < 8 < 9 > 0 < 2 < 3 > 1 < 7 > 4

여러분은 제시된 k개의 부등호 순서를 만족하는 (k+1)자리의 정수 중에서 최댓값과 최솟값을 찾아야 한다. 앞서 설명한 대로 각 부등호의 앞뒤에 들어가는 숫자는 { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 }중에서 선택해야 하며 선택된 숫자는 모두 달라야 한다. 

• 입력

첫 줄에 부등호 문자의 개수를 나타내는 정수 k가 주어진다. 그 다음 줄에는 k개의 부등호 기호가 하나의 공백을 두고 한 줄에 모두 제시된다. k의 범위는 2 ≤ k ≤ 9 이다. 

• 출력

여러분은 제시된 부등호 관계를 만족하는 k+1 자리의 최대, 최소 정수를 첫째 줄과 둘째 줄에 각각 출력해야 한다. 단 아래 예(1)과 같이 첫 자리가 0인 경우도 정수에 포함되어야 한다. 모든 입력에 답은 항상 존재하며 출력 정수는 하나의 문자열이 되도록 해야 한다. 

• 예제 입력

2
< >

9
> < < < > > > < <

• 예제 출력

897
021

9567843012
1023765489

• 접근방식

k의 범위가 2<=k<=9 이기 때문에 경우의수는 10! = 360만정도 인데 1억 이하는 완전탐색으로 풀어도 괜찮다.

1. 숫자를 문자로 바꿔서 비교해야함 '1' 과 1은 다름
2. 범위에 들어갈수 있는 수를 체크
3. 사용한 수는 재사용하지 않는 visited 필요, 탐색을 마치면 다음 탐색을 위해 원복도 필요
4. 최소를 판별하면서 반복

• 코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>

using namespace std;

int n, visited[10];
char a[20];
vector<string> result;

bool compare(char x, char y, char op)
{
    if (x < y && op == '<')
    {
        return true;
    }
    else if (x > y && op == '>')
    {
        return true;
    }
    else
    {
        return false;
    }
}

void check(int idx, string num)
{
    if (idx == n + 1)
    {
        result.push_back(num);
        return;
    }
    for (int i = 0; i <= 9; i++)
    {
        if (visited[i])  continue;
        if (idx == 0 || compare(num[idx - 1], i + '0', a[idx - 1])) // 숫자를 문자로 만들어주기 아스키 코드로 '0'은 48
        {
            visited[i] = 1;
            check(idx + 1, num + to_string(i));
            visited[i] = 0;
        }
    }
}

int main()
{
    cin >> n;

    for (int i = 0; i < n; i++)
    {
        cin >> a[i];
    }

    check(0, "");
    cout << result[result.size() - 1] << endl << result[0];

    return 0;
}

• 문제링크 : https://www.acmicpc.net/problem/2529

• 문제

지민이는 N개의 물병을 가지고 있다. 각 물병에는 물을 무한대로 부을 수 있다. 처음에 모든 물병에는 물이 1리터씩 들어있다. 지민이는 이 물병을 또 다른 장소로 옮기려고 한다. 지민이는 한 번에 K개의 물병을 옮길 수 있다. 하지만, 지민이는 물을 낭비하기는 싫고, 이동을 한 번보다 많이 하기는 싫다. 따라서, 지민이는 물병의 물을 적절히 재분배해서, K개를 넘지 않는 비어있지 않은 물병을 만들려고 한다.

물은 다음과 같이 재분배 한다.

먼저 같은 양의 물이 들어있는 물병 두 개를 고른다. 그 다음에 한 개의 물병에 다른 한 쪽에 있는 물을 모두 붓는다. 이 방법을 필요한 만큼 계속 한다.

이런 제약 때문에, N개로 K개를 넘지않는 비어있지 않은 물병을 만드는 것이 불가능할 수도 있다. 다행히도, 새로운 물병을 살 수 있다. 상점에서 사는 물병은 물이 1리터 들어있다.

예를 들어, N=3이고, K=1일 때를 보면, 물병 3개로 1개를 만드는 것이 불가능하다. 한 병을 또다른 병에 부으면, 2리터가 들어있는 물병 하나와, 1리터가 들어있는 물병 하나가 남는다. 만약 상점에서 한 개의 물병을 산다면, 2리터가 들어있는 물병 두 개를 만들 수 있고, 마지막으로 4리터가 들어있는 물병 한 개를 만들 수 있다.

• 입력

첫째 줄에 N과 K가 주어진다. N은 107보다 작거나 같은 자연수이고, K는 1,000보다 작거나 같은 자연수이다.

• 출력

첫째 줄에 상점에서 사야하는 물병의 최솟값을 출력한다. 만약 정답이 없을 경우에는 -1을 출력한다.

• 예제 입력

3 1

13 2

1000000 5

• 예제 출력

1

3

15808

• 접근방식

물통을 사지 않고 최대로 물병을 합쳤을 경우

N=2, {1,1} > {2} > 1병
N=3, {1,1,1} > {2,1} > 2병
N=4, {1,1,1,1} > {2,2} > {4} > 1병
N=5, {1,1,1,1,1} > {2,2,1} > {4,1} > 2병
N=6, {1,1,1,1,1,1} > {2,2,2} > {4,2} > 2병
N=7, {1,1,1,1,1,1,1} > {2,2,2,1} > {4,2,1} > 3병

즉, 물병을 하나도 사지않고 N이 2의 n제곱승일 경우 물병을 1병으로 합칠수 있음, 새로운 물병을 살 수 있으니 물병을 계속 구매할경우 물병의 개수가 결국 2의 n제곱승이 된다. (정답이 없을경우가 없음)

n은 주어진 물병의 개수, cnt는 들고가는 물병, result은 상점에서 구매한 물병의 수
1. 주어진 물병을 최대한 합침 (n을 2로 나누기)
2. 나머지가 발생하면 합쳐지지 않은 물병 존재, cnt++
3. n이 0이 될때까지 1~2반복
4. cnt의 개수가 k 이하일 때 result 출력, 아니면 1~3번 반복

• 코드

#include <iostream>
#include <algorithm>

using namespace std;

int n, k, cnt, result;

int main()
{
    cin >> n >> k;

    // n은 주어진 물병의 개수, cnt는 들고가는 물병, result은 상점에서 구매한 물병의 수
    // 1. 주어진 물병을 최대한 합침 (n을 2로 나누기)
    // 2. 나머지가 발생하면 합쳐지지 않은 물병 존재, cnt++
    // 3. n이 0이 될때까지 1~2반복
    // 4. cnt의 개수가 k 이하일 때 result 출력, 아니면 1~3번 반복
    for (result = 0; ; result++) // 
    {
        int temp = n + result; // 상점에서 산 물병 개수 + 주어진 물병의 개수
        cnt = 0;

        while (temp) // temp != 0
        {
            if (temp % 2 == 1)
            {
                cnt++;
            }
            temp /= 2;
        }

        if (cnt <= k)   break;
    }
    cout << result;
    return 0;
}

• 문제링크 : https://www.acmicpc.net/problem/1052

• 문제

Day Of Mourning의 기타리스트 강토가 사용하는 기타에서 N개의 줄이 끊어졌다. 따라서 새로운 줄을 사거나 교체해야 한다. 강토는 되도록이면 돈을 적게 쓰려고 한다. 6줄 패키지를 살 수도 있고, 1개 또는 그 이상의 줄을 낱개로 살 수도 있다.

끊어진 기타줄의 개수 N과 기타줄 브랜드 M개가 주어지고, 각각의 브랜드에서 파는 기타줄 6개가 들어있는 패키지의 가격, 낱개로 살 때의 가격이 주어질 때, 적어도 N개를 사기 위해 필요한 돈의 수를 최소로 하는 프로그램을 작성하시오.

• 입력

첫째 줄에 N과 M이 주어진다. N은 100보다 작거나 같은 자연수이고, M은 50보다 작거나 같은 자연수이다. 둘째 줄부터 M개의 줄에는 각 브랜드의 패키지 가격과 낱개의 가격이 공백으로 구분하여 주어진다. 가격은 0보다 크거나 같고, 1,000보다 작거나 같은 정수이다.

• 출력

첫째 줄에 기타줄을 적어도 N개 사기 위해 필요한 돈의 최솟값을 출력한다.

• 예제 입력

4 2
12 3
15 4

10 3
20 8
40 7
60 4

15 1
100 40

17 1
12 3

7 2
10 3
12 2

9 16
21 25
77 23
23 88
95 43
96 19
59 36
80 13
51 24
15 8
25 61
21 22
3 9
68 68
67 100
83 98
96 57

• 예제 출력

12

36

300

36

12

6

• 접근방식

패키지와 단품 가격 둘 다 제일 낮은 가격을 저장하고 경우의 수중에 가장 작은 수를 고르면 된다.

1) 단품만 구매했을 경우

n * 제일 낮은 단품 가격

2) 패키지만 구매했을 경우

(n / 6) * 제일 낮은 패키지 가격

단, n % 6 != 0 즉, 6개로 나눠 떨어지지 않을 때 하나를 더 구매해야한다.

3) 패키지 + 단품을 구매했을 경우

(n / 6) * 제일 낮은 패키지 가격 + (n % 6) * 제일 낮은 단품 가격

• 코드

#include <iostream>
#include <algorithm>

using namespace std;

int n, m, package, single, result;
int min_package = 1000, min_single = 1000;

int main()
{
    cin >> n >> m;

    for (int i = 0; i < m; i++)
    {
        cin >> package >> single;
        // 패키지와 단품 가격 둘 다 제일 낮은 가격 저장
        min_package = min(min_package, package);
        min_single = min(min_single, single);
    }

    int case_1, case_2, case_3;

    case_1 = n * min_single; // 단품만 골랐을 경우 case_1
    case_2 = (n / 6) * min_package; // 패키지만 골랐을 경우 case_2
    if (n % 6 != 0) case_2 += min_package; // 나머지가 있는경우 패키지 한 번 더사기
    case_3 = (n / 6) * min_package + (n % 6) * min_single; // 단품 + 패키지를 골랐을 경우 case_3

    result = min(case_1, min(case_2, case_3));

    cout << result;

    return 0;
}

• 문제링크 : https://www.acmicpc.net/problem/1049

• 문제

옛날 옛적에 수학이 항상 큰 골칫거리였던 나라가 있었다. 이 나라의 국왕 김지민은 다음과 같은 문제를 내고 큰 상금을 걸었다.

길이가 N인 정수 배열 A와 B가 있다. 다음과 같이 함수 S를 정의하자.

S = A[0] × B[0] + ... + A[N-1] × B[N-1]

S의 값을 가장 작게 만들기 위해 A의 수를 재배열하자. 단, B에 있는 수는 재배열하면 안 된다.

S의 최솟값을 출력하는 프로그램을 작성하시오.

• 입력

첫째 줄에 N이 주어진다. 둘째 줄에는 A에 있는 N개의 수가 순서대로 주어지고, 셋째 줄에는 B에 있는 수가 순서대로 주어진다. N은 50보다 작거나 같은 자연수이고, A와 B의 각 원소는 100보다 작거나 같은 음이 아닌 정수이다.

• 출력

첫째 줄에 S의 최솟값을 출력한다.

• 예제 입력

5
1 1 1 6 0
2 7 8 3 1

3
1 1 3
10 30 20

9
5 15 100 31 39 0 0 3 26
11 12 13 2 3 4 5 9 1

• 예제 출력

18

80

528

• 접근방식

A의 가장 작은수 * B의 가장 큰수 순으로 구하면 된다 즉, A를 오름차순, B를 내림차순으로 정렬하면 간단하게 해결되지만 문제의 조건인 B를 재배열하지 말라는 것을 지키려한다.

B에서 가장 큰수의 인덱스를 구해서 해당 인덱스의 요소를 식에 대입하면 된다. 이렇게 하면 재배열은 아니니깐..?? A를 재배열 하려면 결국 B의 요소들과 비교해야하는데 따로 저장해두는거 아니면 답이 없다고 생각한다.

• 코드

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int n, result;
int a[54], b[54];

int main()
{
    cin >> n;

    for (int i = 0; i < n; i++)
    {
        cin >> a[i];
    }

    for (int i = 0; i < n; i++)
    {
        cin >> b[i];
    }

    // 단순히 a는 오름차순, b는 내림차순으로 풀 수 있으나
    // 문제에서 b는 재배열하지 말라는 것을 지켜보기
    // 1. a를 먼저 오름차순 정렬
    sort(a, a + n);
    int maxindex = 0;
    int bsize = sizeof(b) / sizeof(b[0]);
    for (int i = 0; i < n; i++)
    {
        // 2. b의 가장 큰 수의 인덱스를 구해서
        maxindex = max_element(b, b + bsize) - b;
        // 3. 식에 대입하기
        result += (a[i] * b[maxindex]);
        // 4. 사용한 b의 가장 큰수는 초기화
        b[maxindex] = 0;
    }

    cout << result;
    return 0;
}

• 문제링크 : https://www.acmicpc.net/problem/1026