'코딩테스트' 카테고리의 글 목록 (2 Page)

728x90

1. 문제

https://www.acmicpc.net/problem/18111

18111번: 마인크래프트

팀 레드시프트는 대회 준비를 하다가 지루해져서 샌드박스 게임인 ‘마인크래프트’를 켰다. 마인크래프트는 1 × 1 × 1(세로, 가로, 높이) 크기의 블록들로 이루어진 3차원 세계에서 자유롭게

www.acmicpc.net

2. 접근 방식

1차 : 전체 블록의 평균(높이)을 구해서 해당 높이까지 블록을 맞춰주는 로직 작성 -> 틀림
2차 : 0~가장 큰 높이의 블록을 기준으로 각 케이스를 계산하여 가장 시간이 빠른 경우 선택 -> 1%에서 틀림
3차 : 위와 동일하지만 블록을 먼저 다 회수하고 설치 진행 -> 시간초과
4차 : 제거할 블록과 쌓을 블록의 개수를 구하고 시간을 나중에 구함 -> 통과

3. 반례

// 1 64
3 4 1
64 64 64 64
64 64 64 64
64 64 64 63

// 22 63
3 4 0
64 64 64 64
64 64 64 64
64 64 64 63

// 2 0
3 4 99
0 0 0 0
0 0 0 0
0 0 0 1

// 2 1
1 3 68
0 0 1

// 250 35
3 4 11
29 51 54 44
22 44 32 62
25 38 16 2

// 355 32 
4 4 36
15 43 61 21
19 33 31 55
48 63 1 30
31 28 3 8

// 0 0
1 1 0
0

// 768 128
2 2 0
256 256
0 0

// 879 10
7 7 6000
30 21 48 55 1 1 4
0 0 0 0 0 0 0
15 4 4 4 4 4 8
20 40 60 10 20 30 2
1 1 1 1 1 1 9
24 12 33 7 14 25 3
3 3 3 3 3 3 32

// 350 40
2 2 35
20 10
190 40

// 290 170
2 2 68
120 90
250 170

4. 코드

1차 코드 : 동일한 시간일 경우 높은 높이 조건을 충족하지 못함. ( + 틀린 케이스 존재)

#include<iostream>
#include<cmath>

using namespace std;

int main() {
    int n, m, inventory, height, time = 0;
    double sum = 0;

    cin >> n >> m >> inventory;

    // 맵 입력
    int** map = new int*[n];
    for (int i = 0; i < n; i++) {
        map[i] = new int[m];
        for (int j = 0; j < m; j++) {
            cin >> map[i][j];
            sum += map[i][j];
        }
    }

    // 전체 높이 결정 (인벤토리 기준)
    if (inventory > 0) {
        height = round(sum / (n * m));
    }
    else {
        height = floor(sum / (n * m));
    }
    
    // 땅 다듬기
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (map[i][j] == height)
                continue;

            if (map[i][j] > height) {
                time += 2;
                map[i][j] -= 1;
                inventory++;
            }
            else {
                time += 1;
                map[i][j] += 1;
                inventory--;
            }

        }
    }

    cout << time << " " << height << "\n";
    
    return 0;
}

2차 코드 : 틀린 케이스 존재 (앞에부터 가져와서 쌓기 때문에 블록이 부족한 경우 발생)

#include<iostream>
#include<cmath>

using namespace std;

// 현재 맵에서 입력된 높이까지 얼마의 시간이 걸리는지 반환
int func_18111_getTime(int height, int n, int m, int inventory, int **map) {
    int time = 0, tmp_map;
    bool flag = true;

    // map 전체 스캔
    for (int i = 0; i < n && flag; i++) {
        for (int j = 0; j < m && flag; j++) {
            tmp_map = map[i][j];

            if (tmp_map == height)
                continue;
			
            // 현재 블록의 높이가 원하는 높이보다 높으면 블록 회수
            if (tmp_map > height) {
                while (tmp_map != height) {
                    time += 2;
                    tmp_map -= 1;
                    inventory++;
                }
            }
            else {
                // 블록 설치 (인벤토리가 부족하면 flag == false
                while (tmp_map != height) {
                    if (inventory > 0) { 
                        inventory--; 
                    }
                    else {
                        flag = false;
                    }

                    if (!flag) 
                        break;

                    time += 1;
                    tmp_map += 1;
                }

                if (!flag || tmp_map != height) {
                    flag = false;
                    break;
                }
            }

        }
    }
    
    // flag 가 false 면 time 초기화
    if (!flag) {
        time = 0;
    }

    return time;
}

int main() {
    int n, m, inventory, height=-1, time = 0, tmp, min = 2100000000, max=0;
    double sum = 0;

    cin >> n >> m >> inventory;

	// 맵 정보 입력 및 블록 최대값 구하기
    int** map = new int* [n];
    for (int i = 0; i < n; i++) {
        map[i] = new int[m];
        for (int j = 0; j < m; j++) {
            cin >> map[i][j];
            if (max < map[i][j]) {
                max = map[i][j];
            }
        }
    }
    
    // 0 ~ 블록 최대 값 중 시간이 가장 빠르고, 높이가 높은 값 찾기
    for (int i = 0; i <= max; i++) {
        tmp = func_18111_getTime(i, n, m, inventory, map);

        if (min >= tmp && tmp > 0) {
            if (min == tmp && height > i) continue;
            min = tmp;
            height = i;
        }
    }

    // 찾을 수 없으면 0으로 초기화
    if (min == 2100000000 || height == -1) {
        min = 0;
        height = 0;
    }
    
    cout << min << " " << height << "\n";
    
    return 0;
}

3차 코드 : 입력 높이(height)보다 높은 블록들 먼저 회수하고, 낮은 블록 쌓기

#include<iostream>
#include<cmath>

using namespace std;

int func_18111_getTime(int height, int n, int m, int inventory, int **map) {
    int time = 0, tmp_map;
    bool flag = true;

    // 블록 회수 (높이 낮추기)
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            tmp_map = map[i][j];

            if (tmp_map == height)
                continue;
            
            if (tmp_map > height) {
                while (tmp_map != height) {
                    time += 2;
                    tmp_map -= 1;
                    inventory++;
                }
            }
        }
    }
    
    // 블록 설치 (부족하면 flag == false)
    for (int i = 0; i < n && flag; i++) {
        for (int j = 0; j < m && flag; j++) {
            tmp_map = map[i][j];

            if (tmp_map == height)
                continue;

            if (tmp_map < height) {
                while (tmp_map != height) {
                    if (inventory > 0) {
                        inventory--;
                    }
                    else {
                        flag = false;
                    }

                    if (!flag)
                        break;

                    time += 1;
                    tmp_map += 1;
                }

                if (!flag || tmp_map != height) {
                    flag = false;
                    break;
                }
            }
        }
    }

    if (!flag) {
        time = 0;
    }

    return time;
}

int main() {
    int n, m, inventory, height=-1, time = 0, tmp, min = 2100000000, max=0;
    double sum = 0;

    cin >> n >> m >> inventory;

    int** map = new int* [n];
    for (int i = 0; i < n; i++) {
        map[i] = new int[m];
        for (int j = 0; j < m; j++) {
            cin >> map[i][j];
            if (max < map[i][j]) {
                max = map[i][j];
            }
        }
    }
    
    for (int i = 0; i <= max; i++) {
        tmp = func_18111_getTime(i, n, m, inventory, map);

        if (min >= tmp && tmp > 0) {
            if (min == tmp && height > i) continue;
            min = tmp;
            height = i;
        }
    }

    if (min == 2100000000 || height == -1) {
        min = 0;
        height = 0;
    }
    
    cout << min << " " << height << "\n";
    
    return 0;
}

4차 코드 : 통과

#include<iostream>
#include<cmath>

using namespace std;

int main() {
    int n, m, inventory, min = 2100000000, max = 0;
    int height = -1, time = 0, tmp_block, time_min= 2100000000;
    double sum = 0;

    cin >> n >> m >> inventory;

    // 맵 입력
    int** map = new int* [n];
    for (int i = 0; i < n; i++) {
        map[i] = new int[m];
        for (int j = 0; j < m; j++) {
            cin >> map[i][j];

            if (max < map[i][j]) {
                max = map[i][j];
            }

            if (min > map[i][j]) {
                min = map[i][j];
            }
        }
    }

    int build_block, remove_block;

    // 맵의 최소 블록 높이부터 가장 높은 블록까지 반복
    for (int h = min; h <= max; h++) {
        build_block = 0;
        remove_block = 0;

        // h에서의 회수할 블록, 설치할 블록 개수 구하기
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                tmp_block = map[i][j];

                // 현재 블록이 h보다 낮으면 설치할 블록 개수 누적
                if (h > tmp_block) {
                    build_block += h - tmp_block;
                }

                // 현재 블록이 h 보다 높으면 회수할 블록 개수 누적
                if (h < tmp_block) {
                    remove_block += tmp_block - h;
                }
            }
        }

        // 설치할 블록 개수가 인벤토리와 회수한 블록의합보다 부족한지 검사
        if (build_block <= remove_block + inventory) {
            time = remove_block * 2 + build_block;

            if (time_min >= time) {
                if (height > h) continue;
                time_min = time;
                height = h;
            }
        }
    }

    cout << time_min << " " << height << "\n";
    
    return 0;
}

5. 결과

728x90

저작자표시 비영리 동일조건

'코딩테스트 > 백준' 카테고리의 다른 글

[백준] 10026번 - 적록색약 (골드 5) (0)	2022.04.04
[백준] 10773번 - 제로 (실버 4) (0)	2022.03.15
[백준] 15829번 - Hashing (브론즈 2) (0)	2022.03.15
[백준] 1009번 - 분산처리 (브론즈 3) (0)	2022.03.10
[백준] 삼성 SW 역량 테스트 기출 문제 (작성중) (0)	2022.02.22
[백준] 단계별로 풀어보기 > 그리디 알고리즘 (c++) (0)	2022.02.20

728x90

1. 문제

https://www.acmicpc.net/problem/1009

1009번: 분산처리

입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트 케이스에 대해 정수 a와 b가 주어진다. (1 ≤ a < 100, 1 ≤ b < 1,000,000)

www.acmicpc.net

2. 접근 방식

mod연산의 성질을 통해 큰 제곱수를 연산하지 않고 mod 값을 알아냄
빠른 모듈로 거듭제곱법을 적용함

3. 코드

#include <iostream>
#include <vector>

using namespace std;

typedef unsigned long long ll;

int func_1009_mod(int a, int b) {
    vector<int> tmp, tmp2;
    int *x;
    ll res = 1;

    while(b!=0) {
        tmp.push_back(b % 2);
        b /= 2;
    }

    x = new int[21];
    x[0] = a % 10;
    for (int j = 1; j <= 20; j++) {
        x[j] = (x[j-1] * x[j - 1]) % 10;
    }

    for (int i = 0; i < tmp.size(); i++) {
        if (tmp.at(i) == 1) {
            res *= x[i];
        }
    }

    if (res % 10 == 0) res = 10;
    else res %= 10;
    
    return res;
}

int main() {
    int n, a, b;
    cin >> n;

    for (int i = 0; i < n; i++) {
        cin >> a >> b;
        cout << func_1009_mod(a, b) << "\n";
    }
    
    return 0;
}

4. 결과

C++로 구현시 큰 수를 변수 하나로 처리하기 어려워 다른 방법을 찾아야했지만, 파이썬을 활용하면 Pow 연산만으로 결과를 구할 수 있음
파이썬 활용하면 좋은 문제인듯함

728x90

저작자표시 비영리 동일조건

'코딩테스트 > 백준' 카테고리의 다른 글

[백준] 10773번 - 제로 (실버 4) (0)	2022.03.15
[백준] 15829번 - Hashing (브론즈 2) (0)	2022.03.15
[백준] 18111번 - 마인크래프트 (실버 2) (0)	2022.03.14
[백준] 삼성 SW 역량 테스트 기출 문제 (작성중) (0)	2022.02.22
[백준] 단계별로 풀어보기 > 그리디 알고리즘 (c++) (0)	2022.02.20
[백준] 단계별로 풀어보기 > 동적 계획법 1 (c++) (0)	2022.02.16

728x90

목적

하노이의 탑 알고리즘을 가시화하여 이해를 쉽게함
가시화된 알고리즘을 재귀 함수로 구현함
구현할 함수는 아래 2개임 ( A탑에 위치한 원반 개수는 N)
int count_hanoi(int n) : A에서 C까지 N개의 원판을 이동시키는데 필요한 전체 개수
void hanoi(int n, int from, int to) : n번째 원판을 From에서 To로 이동시킴

탑 이동 알고리즘 (Hanoi Function)

하노이 탑의 이동을 재귀로 구현할 땐 아래 이미지의 이동 방식을 알면 됨

N이 2보다 더 큰 경우도 가장 밑에 있는 N번째 원판과 그위의 나머지 원판으로 부분을 나누면,
위와 같은 방식으로 이동이 가능함

hanoi(2, A, B)와 hanoi(2, B, C)의 이동을 직접 나열해보면 아래와 같다

hanoi(n, from, to) 함수는 아래와 같은 규칙을 갖는다.

원판의 개수로 전체 이동 횟수 구하기 (Count_Hanoi Function)

하노이 탑의 이동 횟수는 아래와 같은 형태의 수열을 이루고 있다.

원판의 개수가 N일 때, 원판을 이동 시키는 횟수는 '2의 N제곱 -1' (2^n -1)
제곱연산은 1 << N으로도 표현이 가능함 (비트연산)
Ex) 0001 << 3 -> 1000(2), 8(10)
원판 개수 = 1 << N -1

소스 코드

아래 코드에선 탑을 1~3으로 표현함.

#include<iostream>

using namespace std;

void count_hanoi(int n){
	cout << (1 << n) -1 << "\n";
}

void hanoi(int n, int from, int to) {
	if (n == 1){
		cout << from << " " << to << "\n";
	}else{
		hanoi(n - 1, from, 6 - from - to);
		cout << from << " " << to << "\n";
		hanoi(n - 1, 6 - from - to, to);
	}
}

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

	count_hanoi(n);
	hanoi(n, 1, 3);
    
	return 0;
}

결과

728x90

저작자표시 비영리 동일조건

'코딩테스트 > 알고리즘' 카테고리의 다른 글

[알고리즘] 순열과 조합 (0)	2022.04.21
[알고리즘] 다익스트라(Dijkstra) (0)	2022.04.11
[자료구조] 우선순위 큐 - 작성 중 (0)	2022.04.11
[알고리즘] DFS/ BFS (0)	2022.02.05
[알고리즘] 달팽이 배열 채우기 (0)	2021.11.06
[알고리즘] 함수 (0)	2021.10.11

728x90