[문제 링크]

 

1748번: 수 이어 쓰기 1

첫째 줄에 N(1≤N≤100,000,000)이 주어진다.

www.acmicpc.net

i = 1부터 N까지 반복할때마다 i의 자릿수를 sum변수에 더해주면 원하는 결과를 얻을 수 있다.

#include <iostream>
#include <cmath>
using namespace std;
 
int main(void)
{
    int num;
    cin >> num;
    int temp = num, digit = 1;
    while ((temp / 10) != 0) 
        temp /= 10, digit++;
 
    int i=1, sum = 0, digitNum = 1,digitMax = 10;
    while (digit--)
    {
        for ( ; i < digitMax; i++)
        {
            if (i > num)
            {
                cout << sum << endl;
                return 0;
            }
            else
            {
                sum += digitNum;
            }
        }
        digitNum++;
        digitMax *= 10;
    }
}
http://colorscripter.com/info#e" target="_blank" style="color:#e5e5e5text-decoration:none">Colored by Color Scripter

알고리즘 200일 프로젝트 - 15day

내일도 열심히!

저작자표시 비영리

'알고리즘 > BOJ' 카테고리의 다른 글

백준 15684번: 사다리 조작 (c++)  (0) 2020.04.22
백준 10448: 유레카 이론 (c++)  (0) 2020.04.21
백준 12100번: 2048(Easy) (C++)  (0) 2020.04.19
백준 15683번: 감시 (C++)  (0) 2020.04.18
백준 1065번: 한수  (0) 2020.04.17

[문제 링크]

 

12100번: 2048 (Easy)

첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다. 블록에 쓰여 있는 수는 2보다 크거나 같고, 1024보다 작거나 같은 2의 제곱꼴이다. 블록은 적어도 하나 주어진다.

www.acmicpc.net

이것저것 생각할 게 많아서 재미있는 문제였다.

알고리즘은 다음과 같다.

한번 움직이는데 가능한 경우의 수는 위 아래 왼쪽 오른쪽 4개의 경우가 있으며 최대 5번 움직이기 때문에 움직일 수 있는 모든 경우의 수를 다해보고, 움직인 횟수가 5번이 됐을 때를 기저사례로 추가하여 보드의 최댓값을 변수에 저장해주면 된다.

같은 숫자일때 합쳐지는 것과 움직이는 방향에 따라 합쳐지는 우선순위가 다르다는 점을 구현하기 위해 Queue를 사용하였다.

 

위로 올리는 경우를 예로 들면,

1. 동일한 x좌표 상에서 y좌표만 0부터 N-1까지 차례대로 큐에 넣는다.

2. 큐의 첫번째 원소를 first, 두번째 원소를 second에 저장하고 저장한 원소는 제거한다.

if (0은 빈 칸을 뜻하므로 first또는 second에 0이 저장되있다면 다시 2번 과정을 반복한다.)

if (큐가 비어있는지 확인하고 비어있다면 위 과정은 건너뛴다.)

3. first와 second가 같은 숫자라면 first * 2한 값을 board[0][x]에 넣어주고, first = 0, second = 0 으로 바꿔준다.

다른 숫자라면 first를 board[0][x]에 넣어주고 first = second, second = 0 으로 바꿔준다.

4. y좌표가 N-1이 될 때까지 y를 1 증가시키면서 2, 3번 과정을 반복한다.

5. x좌표가 N-1이 될 때까지 x를 1증가시키면서 1번~4번 과정을 반복한다.

 

위의 과정을 위, 아래, 왼쪽, 오른쪽의 경우에 대해 각각 다르게 구현해준 다음, 모든 경우의 수를 완전탐색하면 원하는 결과를 얻을 수 있다.

지금 보여드리는 코드는 중복되는 코드를 최대한 줄여놓은 코드입니다.

이해하기 힘드신분들을 위해 줄이기 전 코드도 함께 첨부해드릴게요.

더보기
#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
 
int board[21][21];
int maxLen;
int maxNum = -987654321;
int max(int a, int b) { return a > b ? a : b; }
void Solution(int moveCnt);    // 전방선언
void AddBoard(queue<int>& tempQ, int here, int type)
{
    int fir = 0, sec = 0;
    for (int i = 0; i < maxLen; i++)
    {
        while (!tempQ.empty())
        {
            int n = tempQ.front();
            tempQ.pop();
            if (fir == 0) fir = n;
            else if (sec == 0) sec = n;
            if (fir != 0 && sec != 0) break;
        }
        switch (type)
        {
        case 0:    // 위로 올렸을 때
            if (fir == sec)
            {
                board[i][here] = fir * 2;
                fir = 0, sec = 0;
            }
            else
            {
                board[i][here] = fir;
                fir = sec, sec = 0;
            }
            break;
        case 1:    // 아래로 내렸을 때
            if (fir == sec)
            {
                board[maxLen - 1 - i][here] = fir * 2;
                fir = 0, sec = 0;
            }
            else
            {
                board[maxLen - 1 - i][here] = fir;
                fir = sec, sec = 0;
            }
            break;
        case 2:    // 오른쪽으로 밀었을 때
            if (fir == sec)
            {
                board[here][i] = fir * 2;
                fir = 0, sec = 0;
            }
            else
            {
                board[here][i] = fir;
                fir = sec, sec = 0;
            }
            break;
        case 3:    // 왼쪽으로 밀었을 때
            if (fir == sec)
            {
                board[here][maxLen - 1 - i] = fir * 2;
                fir = 0, sec = 0;
            }
            else
            {
                board[here][maxLen - 1 - i] = fir;
                fir = sec, sec = 0;
            }
 
        }
    }
}
void MovingBoard(int type, int moveCnt)
{
    queue<int> tempQ;
    switch (type)
    {
    case 0:    // 위로 올렸을 때
        for (int i = 0; i < maxLen; i++)
        {
            for (int j = 0; j < maxLen; j++)
                tempQ.push(board[j][i]);
            AddBoard(tempQ, i, type);
        }
        Solution(moveCnt + 1);
        break;
    case 1:    // 아래로 내렸을 때
        for (int i = 0; i < maxLen; i++)
        {
            for (int j = maxLen - 1; j >= 0; j--)
                tempQ.push(board[j][i]);
            AddBoard(tempQ, i, type);
        }
        Solution(moveCnt + 1);
        break;
    case 2: // 오른쪽으로 밀었을 때
        for (int i = 0; i < maxLen; i++)
        {
            for (int j = 0; j < maxLen; j++)
                tempQ.push(board[i][j]);
            AddBoard(tempQ, i, type);
        }
        Solution(moveCnt + 1);
        break;
    case 3:    // 왼쪽으로 밀었을 때
        for (int i = 0; i < maxLen; i++)
        {
            for (int j = maxLen - 1; j >= 0; j--)
                tempQ.push(board[i][j]);
            AddBoard(tempQ, i, type);
        }
        Solution(moveCnt + 1);
        break;
    }
}
void Solution(int moveCnt)
{
    if (moveCnt == 5)
    {
        for (int i = 0; i < maxLen; i++)
            for (int j = 0; j < maxLen; j++)
                maxNum = max(maxNum, board[i][j]);
        return;
    }
 
    int temp[21][21];
    memcpy(temp, board, sizeof(board));
    int type = 4;
    while (type--)    // 4번 반복(상하좌우)
    {
        MovingBoard(type, moveCnt);
        memcpy(board, temp, sizeof(board));
    }
}
int main(void)
{
    cin >> maxLen;
    int n;
    for (int i = 0; i < maxLen; i++)
        for (int j = 0; j < maxLen; j++)
            cin >> board[i][j];
    Solution(0);
    cout << maxNum << endl;
    return 0;
}
http://colorscripter.com/info#e" target="_blank" style="color:#4f4f4ftext-decoration:none">Colored by Color Scripter
 
#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
 
int board[21][21];
int maxLen;
int maxNum = -987654321;
int max(int a, int b) { return a > b ? a : b; }
void Solution(int moveCnt);    // 전방선언
void AddNumber(int& fir, int& sec, int col, int row)
{
    if (fir == sec)
    {
        board[col][row] = fir * 2;
        fir = 0, sec = 0;
    }
    else
    {
        board[col][row] = fir;
        fir = sec, sec = 0;
    }
}
void AddBoard(queue<int>& tempQ, int here, int type)
{
    int fir = 0, sec = 0;
    for (int i = 0; i < maxLen; i++)
    {
        while (!tempQ.empty())
        {
            int n = tempQ.front();
            tempQ.pop();
            if (fir == 0) fir = n;
            else if (sec == 0) sec = n;
            if (fir != 0 && sec != 0) break;
        }
        switch (type)
        {
        case 0:    // 위로 올렸을 때
            AddNumber(fir, sec, i, here);
            break;
        case 1:    // 아래로 내렸을 때
            AddNumber(fir, sec, maxLen - 1 - i, here);
            break;
        case 2:    // 오른쪽으로 밀었을 때
            AddNumber(fir, sec, here, i);
            break;
        case 3:    // 왼쪽으로 밀었을 때
            AddNumber(fir, sec, here, maxLen - 1 - i);
            break;
        }
    }
}
void Moving(int start, int end, int type, int moveCnt)
{
    queue<int> tempQ;
    for (int i = 0; i < maxLen; i++)
    {
        if (type == 0 || type == 2)    // 위로 올렸을 때 || 오른쪽으로 밀었을 때
            for (int j = start; j < end; j++)
            {
                if (type == 0) 
                    tempQ.push(board[j][i]);
                else 
                    tempQ.push(board[i][j]);
            }
        else // 아래로 내렸을 때 || 왼쪽으로 밀었을 때
            for (int j = start; j >= end; j--)
            {
                if (type == 1) 
                    tempQ.push(board[j][i]);
                else 
                    tempQ.push(board[i][j]);
            }
        AddBoard(tempQ, i, type);
    }
    Solution(moveCnt + 1);
}
void MovingBoard(int type, int moveCnt)
{
    if (type == 0 || type == 2)
        Moving(0, maxLen, type, moveCnt);
    else
        Moving(maxLen - 1, 0, type, moveCnt);
}
void Solution(int moveCnt)
{
    if (moveCnt == 5)    // 기저사례. 5번 이동했다면 보드에서 제일 큰 수 저장
    {
        for (int i = 0; i < maxLen; i++)
            for (int j = 0; j < maxLen; j++)
                maxNum = max(maxNum, board[i][j]);
        return;
    }
    int temp[21][21];
    memcpy(temp, board, sizeof(board));    // 바뀌기 전 보드 저장
    int type = 4;
    while (type--)    // 4번 반복(상하좌우)
    {
        MovingBoard(type, moveCnt);
        memcpy(board, temp, sizeof(temp));    // 복사해놨던 보드로 다시 바꿈
    }
}
int main(void)
{
    cin >> maxLen;
    for (int i = 0; i < maxLen; i++)
        for (int j = 0; j < maxLen; j++)
            cin >> board[i][j];
    Solution(0);
    cout << maxNum << endl;
    return 0;
}
 
http://colorscripter.com/info#e" target="_blank" style="color:#4f4f4ftext-decoration:none">Colored by Color Scripter
 

알고리즘 200일 프로젝트 - 14day

내일도 열심히!

저작자표시 비영리

'알고리즘 > BOJ' 카테고리의 다른 글

백준 10448: 유레카 이론 (c++)  (0) 2020.04.21
백준 1748번: 수 이어 쓰기 1 (C++)  (0) 2020.04.20
백준 15683번: 감시 (C++)  (0) 2020.04.18
백준 1065번: 한수  (0) 2020.04.17
백준 15686번: 치킨 배달 (C++)  (0) 2020.04.15

[문제 링크]

 

15683번: 감시

스타트링크의 사무실은 1×1크기의 정사각형으로 나누어져 있는 N×M 크기의 직사각형으로 나타낼 수 있다. 사무실에는 총 K개의 CCTV가 설치되어져 있는데, CCTV는 5가지 종류가 있다. 각 CCTV가 감시할 수 있는 방법은 다음과 같다. 1번 CCTV는 한 쪽 방향만 감시할 수 있다. 2번과 3번은 두 방향을 감시할 수 있는데, 2번은 감시하는 방향이 서로 반대방향이어야 하고, 3번은 직각 방향이어야 한다. 4번은 세 방향, 5번은 네 방향을 감시할

www.acmicpc.net

내공이 부족한 것을 다시한번 뼈저리게 느낀 문제..

알고리즘은 다음과 같다.

대각선으로는 감시를 못하기 때문에 어떤 cctv든 한쪽 방향에 대해서 y좌표만 1증감하거나, x좌표만 1증감한다.

따라서 코드의 중복을 막기 위해 가로방향과 세로방향에 대해 탐색하는 함수를 만들어 호출하도록 하였다.

1번 cctv는 상 하 좌 우 4개의 경우의 수, 2번 cctv는 상하 좌우 2개의 경우의 수,

3번 cctv는 상좌, 상우, 하좌, 하우 4개의 경우의 수, 4번 cctv는 상좌우 상하좌 상하우 하좌우 4개 경우의 수,

5번은 1개의 경우의 수가 존재하기 때문에 사무실에 존재하는 cctv들의 모든 경우의 수에 대하여 완전탐색하면 원하는 출력을 얻을 수 있다.

실력이 부족하여 코드가 조잡하기 때문에.. 이해하기 힘들 수도 있습니다.

#include <iostream>
#include <cstring>
#include <vector>
using namespace std;
 
const int INF = 987654321;
int maxCol, maxRow;
bool visited[8][8];
int result = INF;
vector<vector<int>> map;
int min(int a, int b) { return a < b ? a : b; }
void Solution();    // 전방선언
void ScanChange(int tempY, int tempX, int scanY, int scanX)
// CCTV가 볼 수 있는 0을 9로 바꿈
{
    if(scanX == 0)
        while (1)
        {
            tempY += scanY;
            if (tempY >= maxCol || tempY < 0) break;
            if (map[tempY][tempX] == 6) break;
            if (map[tempY][tempX] == 0)
                map[tempY][tempX] = 9;
        }
    else
        while (1)
        {
            tempX += scanX;
            if (tempX >= maxRow || tempX < 0) break;
            if (map[tempY][tempX] == 6) break;
            if (map[tempY][tempX] == 0)
                map[tempY][tempX] = 9;
        }
}
void GoScan(int y, int x, int type)
// CCTV 1번부터 5번까지 각각 다르게 동작
{
    vector<vector<int>> temp(map);
    int scan;
    switch (type)
    {
    case 1:
        scan = 1;
        for (int i = 0; i < 2; i++)
        {
            ScanChange(y, x, 0, scan);
            Solution();
            map = temp;
            ScanChange(y, x, scan, 0);
            Solution();
            map = temp;
            scan = -1;
        }
        break;
    case 2:
        ScanChange(y, x, 0, 1);
        ScanChange(y, x, 0, -1);
        Solution();
        map = temp;
 
        ScanChange(y, x, 1, 0);
        ScanChange(y, x, -1, 0);
        Solution();
        break;
    case 3:
        scan = 1;
        for (int i = 0; i < 2; i++)
        {
            ScanChange(y, x, scan, 0);
            ScanChange(y, x, 0, scan);
            Solution();
            map = temp;
 
            ScanChange(y, x, scan, 0);
            ScanChange(y, x, 0, scan*-1);
            Solution();
            map = temp;
            scan = -1;
        }
        break;
    case 4:
        ScanChange(y, x, -1, 0);
        ScanChange(y, x, 0, -1);
        ScanChange(y, x, 0, 1);
        Solution();
        map = temp;
 
        ScanChange(y, x, 0, 1);
        ScanChange(y, x, 1, 0);
        ScanChange(y, x, 0, -1);
        Solution();
        map = temp;
 
        ScanChange(y, x, -1, 0);
        ScanChange(y, x, 0, -1);
        ScanChange(y, x, 1, 0);
        Solution();
        map = temp;
 
        ScanChange(y, x, -1, 0);
        ScanChange(y, x, 0, 1);
        ScanChange(y, x, 1, 0);
        Solution();
        break;
    case 5:
        ScanChange(y, x, 0, 1);
        ScanChange(y, x, 1, 0);
        ScanChange(y, x, 0, -1);
        ScanChange(y, x, -1, 0);
        Solution();
        break;
    }
}
void Solution()
{
    int yPos = -1, xPos = -1;
    for (int i = 0; i < maxCol; i++)
    {
        for (int j = 0; j < maxRow; j++)
        {
            if (!visited[i][j] && map[i][j] != 0 && map[i][j] != 6 && map[i][j] != 9)
            {
                yPos = i;
                xPos = j;
                break;
            }
            if (yPos != -1) break;    // 이중 for문 탈출
        }
    }
    if (yPos == -1)    // 기저사례. 모든 CCTV검사했을 시 사각지대 카운팅
    {
        int cnt = 0;
        for (int i = 0; i < maxCol; i++)
            for (int j = 0; j < maxRow; j++)
                if (map[i][j] == 0) cnt++;
        result = min(result, cnt);
        return;
    }
    visited[yPos][xPos] = true;
    GoScan(yPos, xPos, map[yPos][xPos]);
    visited[yPos][xPos] = false;
}
int main(void)
{
    cin >> maxCol >> maxRow;
    vector<int> temp;
    memset(visited, true, sizeof(visited));
    for (int i = 0; i < maxCol; i++)
    {
        for (int j = 0; j < maxRow; j++)
        {
            int n;
            cin >> n;
            temp.push_back(n);
            if (n != 0 && n != 6)
                visited[i][j] = false;
        }
        map.push_back(temp);
        temp.clear();
    }
    Solution();
    cout << result << endl;
    return 0;
}
http://colorscripter.com/info#e" target="_blank" style="color:#4f4f4ftext-decoration:none">Colored by Color Scripter

알고리즘 200일 프로젝트 - 13day

내일도 열심히!

저작자표시 비영리

'알고리즘 > BOJ' 카테고리의 다른 글

백준 1748번: 수 이어 쓰기 1 (C++)  (0) 2020.04.20
백준 12100번: 2048(Easy) (C++)  (0) 2020.04.19
백준 1065번: 한수  (0) 2020.04.17
백준 15686번: 치킨 배달 (C++)  (0) 2020.04.15
백준 14500번: 테트로미노 (C++)  (0) 2020.04.15

[문제 링크]

 

1065번: 한수

어떤 양의 정수 X의 각 자리가 등차수열을 이룬다면, 그 수를 한수라고 한다. 등차수열은 연속된 두 개의 수의 차이가 일정한 수열을 말한다. N이 주어졌을 때, 1보다 크거나 같고, N보다 작거나 같은 한수의 개수를 출력하는 프로그램을 작성하시오. 

www.acmicpc.net

등차수열 = 증가하거나 감소하는 수치가 일정한 수열

각 자리수마다 0~9의 숫자가 올 수 있으므로 i=0부터 i<10까지 반복문을 만들고

반복문 안에 재귀를 돌려 나오는 모든 경우의 수를 구한다. 재귀호출 할때마다 뽑은 숫자를 배열에 넣었을 때의 정수값(pNum)과 뽑은 숫자의 개수(pick)을 인자로 넘겨주었다. 코드를 본다면 쉽게 이해할 수 있을 것이라 생각한다.

#include <iostream>
#include <vector>
using namespace std;
 
vector<int> picked;
int cNum;
int cArrLen = 1;
int cnt = 0;
void Solution(int pNum, int pick)
{ 
    if (cNum < pNum) return;
    if (pick > 0 && pick <= cArrLen)
    {
        if (pick == 1 || pick == 2) cnt++;
        else
        {
            int comp = picked[0] - picked[1];
            for (int i = 1; i < pick-1; i++)
            {
                if (picked[i] - picked[i + 1] != comp)
                    break;
                cnt++;
            }
        }
    }
    for (int i = 0; i < 10; i++)
    {
        if (pick == 0)
            if (i == 0) continue;
        picked.push_back(i);
        Solution((pNum * 10) + i, pick + 1);
        picked.pop_back();
    }
}
int main(void)
{
    cin >> cNum;
    int temp = cNum;
    while (temp / 10 != 0)
    {
        temp /= 10;
        cArrLen++;
    }
    Solution(0,0);
    cout << cnt << endl;
    return 0;
}
http://colorscripter.com/info#e" target="_blank" style="color:#4f4f4ftext-decoration:none">Colored by Color Scripter

알고리즘 200일 프로젝트 - 12day

내일도 열심히!

저작자표시 비영리

'알고리즘 > BOJ' 카테고리의 다른 글

백준 12100번: 2048(Easy) (C++)  (0) 2020.04.19
백준 15683번: 감시 (C++)  (0) 2020.04.18
백준 15686번: 치킨 배달 (C++)  (0) 2020.04.15
백준 14500번: 테트로미노 (C++)  (0) 2020.04.15
백준 14889번: 스타트와 링크  (0) 2020.04.14

[문제 링크]

 

15686번: 치킨 배달

크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸, 왼쪽에서부터 c번째 칸을 의미한다. r과 c는 1부터 시작한다. 이 도시에 사는 사람들은 치킨을 매우 좋아한다. 따라서, 사람들은 "치킨 거리"라는 말을 주로 사용한다. 치킨 거리는 집과 가장 가까운 치킨집 사이의 거리이다. 즉, 치킨 거리는

www.acmicpc.net

이 문제는 도시 좌표 전체를 배열에 담을 필요 없이 치킨집(2)과 가정집(1) 좌표만 골라서 따로 선언한 배열에 담아주면 쉽게 풀 수 있다.

치킨집 배열에서 M개 치킨집을 살리는 경우를 구한다음, 모든 경우에 따른 치킨거리를 계산하여 최솟값을 출력하면 원하는 결과를 얻을 수 있다.

#include <iostream>
#include <cstdlib>
#include <vector>
using namespace std;
 
const int INF = 987654321;
vector<pair<int, int>> housePos;
vector<pair<int, int>> chickenPos;
vector<int> ckPick;
int ckCnt;
int bestCityDist = INF;
int min(int a, int b) { return a < b ? a : b; }
void ChickenDistance()
{
    int houseLen = housePos.size();
    int cityDist = 0;
    for (int i = 0; i < houseLen; i++)
    {
        int minDistance = INF;
        for (int j = 0; j < ckCnt; j++)
        {
            int yDist = abs(housePos[i].first - chickenPos[ckPick[j]].first);
            int xDist = abs(housePos[i].second - chickenPos[ckPick[j]].second);
            minDistance = min(minDistance, yDist + xDist);
        }
        cityDist += minDistance;
    }
 
    bestCityDist = min(bestCityDist, cityDist);
}
 
void Solution(int start, int pick)
{
    if (pick == ckCnt)
    {
        ChickenDistance();
        return;
    }
    int ckLen = chickenPos.size();
    for (int i = start; i < ckLen; i++)
    {
        ckPick.push_back(i);
        Solution(i + 1, pick+1);
        ckPick.pop_back();
    }
}
int main(void)
{
    int maxLen;
    cin >> maxLen >> ckCnt;
    for (int i = 0; i < maxLen; i++)
        for (int j = 0; j < maxLen; j++)
        {
            int n;
            cin >> n;
            if(n==1)housePos.push_back(pair<int, int>(i, j));
            if(n==2)chickenPos.push_back(pair<int,int>(i, j));
        }
    Solution(0, 0);
    cout << bestCityDist << endl;
    return 0;
}
http://colorscripter.com/info#e" target="_blank" style="color:#4f4f4ftext-decoration:none">Colored by Color Scripter
 

알고리즘 200일 프로젝트 - 10day

내일도 열심히!

저작자표시 비영리

'알고리즘 > BOJ' 카테고리의 다른 글

백준 15683번: 감시 (C++)  (0) 2020.04.18
백준 1065번: 한수  (0) 2020.04.17
백준 14500번: 테트로미노 (C++)  (0) 2020.04.15
백준 14889번: 스타트와 링크  (0) 2020.04.14
백준 1018번: 체스판 다시 칠하기  (0) 2020.04.13

[문제 링크]

 

14500번: 테트로미노

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

www.acmicpc.net

먼저 노트와 펜을 준비한다.

블록의 한 칸을 (y,x)로 잡은다음 나머지 3칸을 기준점과 비교해 y,x 좌표를 적어보자.

그리고 5가지 블록의 회전 모양과 그것을 대칭했을 때 모양에 대한 y,x좌표를 전부 적는다. 

적은 내용을 바탕으로 나올 수 있는 블록 모양을 배열에 담고 보드 (0,0) 좌표에서부터 (N-1,N-1) 까지 모든 칸에 블록을 대보고 그 중에서 최대 점수를 maxScore변수에 저장하고 출력하면 원하는 결과를 얻을 수 있다.

#include <iostream>
#include <vector>
using namespace std;
 
const int dy[19][4] = {
{0,0,0,0}, {0,1,2,3},    // ㅡ
{0,0,1,1},    // ㅁ
{0,1,2,2}, {0,0,0,1}, {0,0,1,2}, {0,0,0,-1}, {0,1,2,2}, {0,0,0,1}, {0,0,1,2}, {0,1,1,1},    // ㄴ
{0,1,1,2}, {0,0,-1,-1}, {0,1,0,-1}, {0,0,1,1},    // ㄱㄴ
{0,0,0,1}, {0,1,2,1}, {0,1,1,1}, {0,1,1,2}    // ㅜ
};
const int dx[19][4] = {
{0,1,2,3}, {0,0,0,0},    // ㅡ
{0,1,0,1},    // ㅁ
{0,0,0,1}, {0,1,2,0}, {0,1,1,1}, {0,1,2,2}, {0,0,0,-1}, {0,1,2,2}, {0,1,0,0}, {0,0,1,2},    // ㄴ
{0,0,1,1}, {0,1,1,2}, {0,0,1,1}, {0,1,1,2},    // ㄱㄴ
{0,1,2,1}, {0,0,0,-1}, {0,-1,0,1}, {0,0,1,0}    // ㅜ
};
 
int board[501][501];
int maxCol, maxRow;
int maxScore = -987654321;
int max(int a, int b) { return a > b ? a : b; }
void SetBlock(int startY, int startX)
{
    int sum;
    for (int i = 0; i < 19; i++)
    {
        sum = 0;
        for (int j = 0; j < 4; j++)
        {
            if (startY + dy[i][j] < 0 || startY + dy[i][j] >= maxCol ||
                startX + dx[i][j] < 0 || startX + dx[i][j] >= maxRow)
                continue;
            sum += board[startY + dy[i][j]][startX + dx[i][j]];
        }
        maxScore = max(maxScore, sum);
    }
}
void Solution()
{
    for (int i = 0; i < maxCol; i++)
        for (int j = 0; j < maxRow; j++)
            SetBlock(i, j);
}
int main(void)
{
    cin >> maxCol >> maxRow;
    for(int i=0; i<maxCol; i++)
        for (int j = 0; j < maxRow; j++)
        {
            cin >> board[i][j];
        }
    Solution();
    cout << maxScore << endl;
    return 0;
}
http://colorscripter.com/info#e" target="_blank" style="color:#4f4f4ftext-decoration:none">Colored by Color Scripter

알고리즘 200일 프로젝트 - 10day

내일도 열심히!

저작자표시 비영리

'알고리즘 > BOJ' 카테고리의 다른 글

백준 1065번: 한수  (0) 2020.04.17
백준 15686번: 치킨 배달 (C++)  (0) 2020.04.15
백준 14889번: 스타트와 링크  (0) 2020.04.14
백준 1018번: 체스판 다시 칠하기  (0) 2020.04.13
백준 1182번: 부분수열의 합  (0) 2020.04.13

[문제 링크]

 

14889번: 스타트와 링크

예제 2의 경우에 (1, 3, 6), (2, 4, 5)로 팀을 나누면 되고, 예제 3의 경우에는 (1, 2, 4, 5), (3, 6, 7, 8)로 팀을 나누면 된다.

www.acmicpc.net

풀이까지 시간이 많이 걸린 문제다. 문제를 잘못 이해하고 접근한 것이 원인이었다.

알고리즘은 다음과 같이 진행된다.

먼저 N명을 입력받고 N*N 배열에 능력치를 입력받는다.

입력받은 N명 중 N/2명으로 팀을 나누는 모든 조합(단, 순서만 다른 조합은 제외)을 구한다.

조합에 속한 원소를 A팀 속하지 않은 원소를 B팀으로 나눠 각 팀의 능력치를 계산하고 A팀과 B팀의 능력치 차이를 구한다음 최솟값을 갱신해주면 원하는 출력을 얻을 수 있다.

#include <iostream>
#include <cstdlib>
#include <vector>
using namespace std;
 
const int INF = 987654321;
vector<vector<int>> member;
vector<int> picked;
vector<bool> visited;
int memNum;
int bestBalance = INF;
int min(int a, int b) { return a < b ? a : b; }
void Solution(int start, int toPick)
{
    if (toPick == memNum / 2)
    {
        int Ateam = 0, Bteam = 0;
        for (int i = 0; i < toPick; i++)    // A팀
            for (int j = 0; j < toPick; j++)
                Ateam += member[picked[i]][picked[j]];
 
        for(int i=0; i< memNum; i++)    // B팀
            for (int j = 0; j < memNum; j++)
            {
                if (visited[i] == true || visited[j] == true) continue;
                Bteam += member[i][j];
            }
        int balance = abs(Ateam - Bteam);
        bestBalance = min(bestBalance, balance);
        return;
    }
    for (int i = start; i < memNum; i++)
    {
        picked.push_back(i);
        visited[i] = true;
        Solution(i+1, toPick + 1);
        picked.pop_back();
        visited[i] = false;
    }
}
int main(void)
{
    cin >> memNum;
    for (int i = 0; i < memNum; i++)
    {
        vector<int> temp;
        for (int j = 0; j < memNum; j++)
        {
            int n;
            cin >> n;
            temp.push_back(n);
        }
        visited.push_back(false);
        member.push_back(temp);
        temp.clear();
    }
    Solution(0,0);
    cout << bestBalance << endl;
    return 0;
}
http://colorscripter.com/info#e" target="_blank" style="color:#4f4f4ftext-decoration:none">Colored by Color Scripter

알고리즘 200일 프로젝트 - 9day

내일도 열심히!

저작자표시 비영리

'알고리즘 > BOJ' 카테고리의 다른 글

백준 15686번: 치킨 배달 (C++)  (0) 2020.04.15
백준 14500번: 테트로미노 (C++)  (0) 2020.04.15
백준 1018번: 체스판 다시 칠하기  (0) 2020.04.13
백준 1182번: 부분수열의 합  (0) 2020.04.13
백준 1966번: 프린터 큐  (0) 2020.04.13

[문제 링크]

 

1018번: 체스판 다시 칠하기

첫째 줄에 N과 M이 주어진다. N과 M은 8보다 크거나 같고, 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 보드의 각 행의 상태가 주어진다. B는 검은색이며, W는 흰색이다.

www.acmicpc.net

먼저, 흰색타일은 1, 검은색타일은 -1이라고 생각하고 풀어보자.

체스판에서 흰색타일(1) 옆은 반드시 검은색타일(-1), 검은색타일(-1) 옆은 반드시 흰색타일(1)이 온다.

따라서 시작타일을 1로 잡고 다음 타일을 검사할 때마다 -1 곱해주면 별도의 체스 보드판을 배열로 정의하지 않아도 문제를 해결할 수 있다.

 
#include <iostream>
#include <vector>
#include <string>
using namespace std;
 
const int MIN = 987654321;
vector<vector<int>> board;
int maxCol, maxRow;
int minCnt = MIN;
int min(int a, int b) { return a < b ? a : b; }
void Solution(int startY, int startX)
{
    if (startY + 8 > maxCol || startX + 8 > maxRow) return;
    int chk = 1;
    int whiteCnt = 0;
    int blackCnt = 0;
    for (int i = startY; i < startY + 8; i++)
    {
        for (int j = startX; j < startX + 8; j++)
        {
            if (board[i][j] != chk) whiteCnt++;
            else blackCnt++;
            chk *= -1;
        }
        chk *= -1;
    }
    int cnt = min(whiteCnt, blackCnt);
    minCnt = min(minCnt, cnt);
    //if(startY+7 < maxCol) Solution(startY + 1, startX);
    //if(startX+7 < maxRow) Solution(startY, startX + 1);
}
int main(void)
{
    cin >> maxCol >> maxRow;
    vector<int> temp;
    for (int i = 0; i < maxCol; i++)
    {
        string wbStr;
        cin >> wbStr;
        for (int j = 0; j < maxRow; j++)
        {
            if (wbStr[j] == 'W') temp.push_back(1);
            else temp.push_back(-1);
        }
        board.push_back(temp);
        temp.clear();
    }
 
    for(int i=0; i < maxCol; i++)
        for(int j=0; j < maxRow; j++)
            Solution(i,j);
 
    cout << minCnt << endl;
    return 0;
}
http://colorscripter.com/info#e" target="_blank" style="color:#4f4f4ftext-decoration:none">Colored by Color Scripter
 

알고리즘 200일 프로젝트 - 8day

처음 컴파일할 땐 위에 주석처리한 코드를 통해 재귀호출했는데 시간초과가 났다. 한참을 삽질하다가

메인함수에서 반복호출하도록 바꿨더니 그제서야 정답 처리를 받을 수 있었다.

두 호출방법에서 어떤 시간차이가 발생했던건지 아직 잘 모르겠다.. 더 공부하면 알 수 있을까?

저작자표시

'알고리즘 > BOJ' 카테고리의 다른 글

백준 14500번: 테트로미노 (C++)  (0) 2020.04.15
백준 14889번: 스타트와 링크  (0) 2020.04.14
백준 1182번: 부분수열의 합  (0) 2020.04.13
백준 1966번: 프린터 큐  (0) 2020.04.13
백준 14888번: 연산자 끼워넣기  (0) 2020.04.12

+ Recent posts

티스토리툴바