'문제풀이/백준' 카테고리의 글 목록 (17 Page)

14500번: 테트로미노

폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변끼리 연결되어 있어야 한다. 즉, 꼭짓점과 꼭짓점만 맞닿아 있으면 안 된다. 정사각형 4개를 이어 붙인 폴리오미노는 테트로미노라고 하며, 다음과 같은 5가지가 있다. 아름이는 크기가 N×M인 종이 위에 테트로미노 하나를 놓으려고 한다. 종이는 1×1 크기의 칸으로 나누

www.acmicpc.net

풀이 ) 완전 탐색

우선 각 테트로미노 모양을 모두 배열 형태로 만들어 놓는다.

이 때 모양이 안겹치고 빠뜨리는 게 없도록 조심해야된다. 필자는 여러 번 실수했다.

그리고 나서는 가장 첫 번째 행 첫 번째 열부터 시작하여 각 모양으로 확인을 한다. 이때 각 행 열이 판에서 벗어나지 않는지 검사를 하여 벗어나는 경우 다음 반복문으로 넘어간다.

#include <cstdio>
#include <algorithm>
using namespace std;

int type[19][3][2] = {{{0, 1}, {0, 2}, {0, 3}},
                    {{1, 0}, {2, 0}, {3, 0}},
                    {{0, 1}, {1, 0}, {1, 1}},
                    {{0, 1}, {0, 2}, {1, 2}},
                    {{0, 1}, {0, 2}, {-1, 2}},
                    {{0, 1}, {0, 2}, {1, 0}},
                    {{0, 1}, {0, 2}, {-1, 0}},
                    {{1, 0}, {2, 0}, {2, 1}},
                    {{1, 0}, {2, 0}, {2, -1}},
                    {{1, 0}, {2, 0}, {0, 1}},
                    {{1, 0}, {2, 0}, {0, -1}},
                    {{1, 0}, {1, 1}, {2, 1}},
                    {{1, 0}, {1, -1}, {2, -1}},
                    {{0, 1}, {1, 1}, {1, 2}},
                    {{0, 1}, {-1, 1}, {-1, 2}},
                    {{1, 0}, {1, 1}, {2, 0}},
                    {{1, 0}, {1, -1}, {2, 0}},
                    {{0, 1}, {1, 1}, {0, 2}},
                    {{0, 1}, {-1, 1}, {0, 2}}};

int main(void)
{
    int n, m, ans = 0, cand, flag, xx, yy;
    int arr[501][501] = {0, };

    scanf("%d%d", &n, &m);

    for(int i  = 0; i < n; ++i)
        for(int j = 0; j < m; ++j)
            scanf("%d", &arr[i][j]);

    for(int i = 0; i < n; ++i){
        for(int j = 0; j < m; ++j){
            for(int k = 0; k < 19; ++k){
                flag = 0;
                for(int l = 0; l < 3; ++l){
                    xx = j+type[k][l][0];
                    yy = i+type[k][l][1];
                    if(xx >= m || xx < 0 || yy >= n || yy < 0){
                        flag++;
                        break;
                    }
                }
                if(flag)
                    continue;
                else{
                    cand = arr[i][j] + arr[i+type[k][0][1]][j+type[k][0][0]] + arr[i+type[k][1][1]][j+type[k][1][0]] + arr[i+type[k][2][1]][j+type[k][2][0]];
                    ans = max(ans, cand);
                }
            }
        }
    }
    printf("%d\n", ans);
    return 0;
}

주의점 )

- 모양 중복

- 종류 수(19가지)

- 인덱스 범위

저작자표시 비영리 변경금지

'문제풀이 > 백준' 카테고리의 다른 글

[C++] 백준 - 10973 : 이전 순열 (0)	2020.03.12
[C++] 백준 - 10972 : 다음 순열 (0)	2020.03.12
[C++] 백준 - 9095 : 1, 2, 3 더하기 (0)	2020.03.12
[C++] 백준 - 1476 : 날짜 계산 (0)	2020.03.10
[C++] 백준 - 2309 : 일곱 난쟁이 (0)	2020.03.10

문제 링크

1476번: 날짜 계산

준규가 사는 나라는 우리가 사용하는 연도와 다른 방식을 이용한다. 준규가 사는 나라에서는 수 3개를 이용해서 연도를 나타낸다. 각각의 수는 지구, 태양, 그리고 달을 나타낸다. 지구를 나타내는 수를 E, 태양을 나타내는 수를 S, 달을 나타내는 수를 M이라고 했을 때, 이 세 수는 서로 다른 범위를 가진다. (1 ≤ E ≤ 15, 1 ≤ S ≤ 28, 1 ≤ M ≤ 19) 우리가 알고있는 1년은 준규가 살고있는 나라에서는 1 1 1로 나타낼 수 있다. 1

www.acmicpc.net

풀이 ) 완전 탐색

서로 다른 세 수에 대해서 나머지라고 생각해서 풀면 되는 문제이다. 공배수 개념

#include <cstdio>
using namespace std;

int main(void)
{
    int e, s, m, ans;
    scanf("%d%d%d", &e, &s, &m);

    ans = e-1;
    while(1){
        if(ans % 28 == s-1 && ans % 19 == m-1)
            break;
        else
            ans += 15;
    }
    printf("%d\n", ans+1);
    return 0;
}

주의점 )

- 예제 입력 4는 반드시 해보기 바란다.

주어지는 e, s, m의 값이 0부터가 아닌 1부터 시작하기 때문에 나머지라고 생각하여 바로 모듈러 연산을 하면 안되고 답 후보에서 1을 뺀 후 출력하기 전에 1을 더해주면 된다.

'문제풀이 > 백준' 카테고리의 다른 글

[C++] 백준 - 10973 : 이전 순열 (0)	2020.03.12
[C++] 백준 - 10972 : 다음 순열 (0)	2020.03.12
[C++] 백준 - 9095 : 1, 2, 3 더하기 (0)	2020.03.12
[C++] 백준 - 14500 : 테트로미노 (0)	2020.03.11
[C++] 백준 - 2309 : 일곱 난쟁이 (0)	2020.03.10

C문제 링크

2309번: 일곱 난쟁이

아홉 개의 줄에 걸쳐 난쟁이들의 키가 주어진다. 주어지는 키는 100을 넘지 않는 자연수이며, 아홉 난쟁이의 키는 모두 다르며, 가능한 정답이 여러 가지인 경우에는 아무거나 출력한다.

www.acmicpc.net

풀이 ) 완전 탐색

일곱 난쟁이의 키의 합이 100이므로 전체 9명의 합을 tot라고 했을 때

완전탐색을 통해서 2명의 합이 tot-100인 조합을 찾는 문제이다.

정렬은 sort()를 사용했다.

#include <cstdio>	// scanf(), printf()
#include <algorithm>	// sort()
using namespace std;

int main(void)
{
    int arr[10] = {0, }, tot = 0;

    for(int i = 0; i < 9; ++i){
        scanf("%d", arr+i);
        tot += arr[i];
    }
    sort(arr, arr+9);

    int flag = 0;
    for(int i = 0; i < 8; ++i){
        for(int j = i; j < 9; ++j){
            if (arr[i]+arr[j] == tot-100){
                arr[i] = 0;
                arr[j] = 0;
                flag++;
                break;
            }
        }
        if(flag)
            break;
    }
    for(int i= 0; i < 9; ++i)
        if(arr[i])
            printf("%d\n", arr[i]);
}

'문제풀이 > 백준' 카테고리의 다른 글

[C++] 백준 - 10973 : 이전 순열 (0)	2020.03.12
[C++] 백준 - 10972 : 다음 순열 (0)	2020.03.12
[C++] 백준 - 9095 : 1, 2, 3 더하기 (0)	2020.03.12
[C++] 백준 - 14500 : 테트로미노 (0)	2020.03.11
[C++] 백준 - 1476 : 날짜 계산 (0)	2020.03.10

공부흔적