개발 블로그

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

15

4
8

접근 방법

이 문제는 보통 투포인터로 많이 푸는 문제이다. 즉, G = (현재+기억)*(현재-기억) 인 점을 활용하여 현재 몸무게와 기억하는 몸무게 간의 관계를 바탕으로 정해진 범위 내에서 몸무게 2개를 조절해가면서(투포인터) 수식을 만족하는 현재 몸무게를 찾는 방식이다. 

나는 G = (현재+기억)*(현재-기억) 에서 

• a = 현재+기억
• b = 현재-기억

a+b  = 2*(현재) 이므로 a+b는 짝수

인 점을 활용했다. 

탐색 범위는 a가 1부터(현재, 기억 모두 자연수이므로 2부터 해도 됨) G까지 했다.

G까지 한 이유는 다음과 같다.

현재와 기억의 최소 차이를 생각해봤을 때 b = 현재-기억 은 양수이므로 현재와 기억 몸무게의 최소 차이는 1이다. 이 경우를 조건의 끝이라고 생각하면 G = a가 된다. 

추가로

1) b = G/a인 점

2) a와 b 모두 양수인 점(a와 b를 곱해서 G가 나와야하며 G는 자연수이므로)

3) 현재 몸무게가 자연수이고, 기억하는 몸무게도 자연수인 점(13번째 line에서 a<=b가 아닌 a<b로 하면 오답으로 나온다. 즉 a>=b인 경우를 고려하면 틀린다는 소리이며 그 중 a=b인 경우가 오답의 원인이 되는 것이다. 아래 링크도 추가 참고하면 기억하는 몸무게도 자연수로 고려해야하는 것 같다.)

https://www.acmicpc.net/board/view/115572

아래 반례가 도움이 되었다. 

https://www.acmicpc.net/board/view/99783

import java.util.*;

public class BOJ_1484_다이어트 {

    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        TreeSet<Integer> set = new TreeSet<Integer>();

        int G = sc.nextInt();
        for(int a = 1; a<=G; a++){	//a 탐색 범위를 1부터 G까지 해야함.
            if(G%a != 0) continue;		//b가 G의 약수가 아니면 패스
            int b = G / a;				//b는 G의 약수 
            if(((a+b) % 2 != 0) || (a<=b)) continue;	//짝수가 아니거나 범위 벗어나면 패스
            set.add((a+b)/2);
        }
        if(set.size() == 0){
            System.out.println(-1);
        }

        else{
            Iterator iter = set.iterator();
            while(iter.hasNext()){
                System.out.println(iter.next());
            }
        }
    }
}

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

문제

서기 2116년, 인간은 더 이상 AI의 상대가 되지 못하게 되었다. 근력, 순발력, 창의력, 사고력, 문제해결능력, 심지어 인간미조차 AI가 인간을 앞선다. AI가 온 지구를 관리하며 이미 인류는 지구의 주인 자리에서 쫓겨난지 오래이다. 그나마 다행인 것은 AI가 인간을 적대적으로 대하지 않고, 도리어 AI가 쌓아올린 눈부신 기술의 발전으로 모든 사람이 무제한적인 재화를 사용할 수 있게 되어 한 세기 전의 사람들이 바라던 돈 많은 백수와 같은 삶을 누릴 수 있게 됐다는 사실이다. 대다수의 인간들은 현재의 상황에 만족하고 더 이상 발전을 포기한 채 놀고 먹으면서 시간을 보내고 있지만 일부 인간들은 인류의 영광을 되찾기 위해 저항군을 조직해 AI에게 투쟁하고 있다.

저항군은 AI에게 승산이 있는 종목을 찾고 있다. 이러한 종목을 가지고 AI에게 승부를 걸어 전 인류에게 도전정신과 인간의 위대함을 증명하고 싶기 때문이다. 저항군의 지도부는 무려 12시간에 걸쳐 AI에게 승산이 있는 종목을 찾기 위한 회의를 진행했다. 회의에서 알고리즘 문제 풀이 대결, 가위불바위총번개악마용물공기보스펀지늑대나무사람뱀 게임, 캐치마인드, 알까기, 스타크래프트, 똥 피하기 게임, 딸기 2비트, 딸기수박당근참외메론 게임, 백일장, 사생 대회 등 다양한 아이디어가 나왔지만 단 0.01%라도 승산이 있어 보이는 종목은 하나도 없었다.

그렇게 모두가 낙담하던 중 누군가가 역사책을 뒤져 인간이 AI에게 승산이 있는 종목을 찾아냈다. 바로 정확히 100년 전에 있었던 이세돌과 알파고의 바둑 대결이었다. 물론 알파고는 그 이후로 발전을 거듭했기에 바둑에서의 승산은 없지만 바둑의 룰을 변형한 Baduk2라는 종목에서는 이세돌이 알파고에게 한 세트를 이긴 것과 같이 인간이 AI에게 승산이 있다고 판단했다.

Baduk2의 룰은 바둑과 거의 유사하지만 양 선수가 돌을 1개씩 번갈아 두는 것이 아니라 2개씩 둔다는 점이 다르다. 서술의 편의를 위해 상하좌우로 인접한 같은 색 돌의 집합을 그룹이라고 하자. 아래의 판에서는 흑의 그룹과 백의 그룹이 각각 3개씩 존재한다.

Baduk2에서는 일반적인 바둑과 동일하게 자신의 돌로 상대방의 그룹을 빈틈없이 에워싸면 갇힌 돌을 죽일 수 있다. 어느 그룹이 빈틈없이 에워싸였다는 것은 그 그룹 내에 빈 칸과 인접해있는 돌이 하나도 없다는 것과 동치이다.

그리고 Baduk2에서는 모든 비어있는 칸에 돌을 둘 수 있다. 설령 상대 돌로 둘러싸여 있어 스스로 잡히는 곳이라고 하더라도 상관이 없다. 아래와 같은 상황을 생각해보자.

두 빨간 칸 모두 백의 입장에서 착수할 경우 연결된 그룹이 흑돌로 둘러싸이게 되어 원래 바둑의 규칙에서는 백의 입장에서 스스로 잡히는 곳이지만 Baduk2에서는 이와 무관하게 백이 빨간 칸 두 곳에 착수해 8개의 흑돌이 들어있는 그룹의 돌을 죽일 수 있다.

저항군은 AI에게 Baduk2로 도전장을 내밀었고 AI는 의외로 순순히 도전을 받아들였다. 이제 저항군은 2116년 3월 9일, 인류의 자존심을 건 Baduk2 대결을 시작한다. 그리고 당신에게 인류의 승리를 돕기 위해 현재 판 위에서 돌 2개를 두어 상대 돌을 최대한 많이 죽이게끔 하는 프로그램을 작성하는 임무가 주어졌다. 인류의 명예를 걸고 현재 판이 주어질 때 돌 2개를 두어 죽일 수 있는 상대 돌의 최대 갯수를 구하는 프로그램을 작성하자.

입력

첫째 줄에 바둑판의 행의 갯수와 열의 갯수를 나타내는 N(3 ≤ N ≤ 20)과 M(3 ≤ M ≤ 20)이 한 칸의 빈칸을 사이에 두고 주어진다. 그 다음 N개의 줄에는 각 줄마다 배열의 각 행을 나타내는 M개의 정수가 한 개의 빈 칸을 사이에 두고 주어진다. 각 칸에 들어가는 값은 0, 1, 2이다. 0은 빈 칸, 1은 나의 돌, 2는 상대의 돌을 의미한다. 빈 칸이 2개 이상 존재함과 현재 바둑판에서 양 플레이어 모두 상대방의 돌로 빈틈없이 에워싸인 그룹이 없음이 모두 보장된다.

출력

첫째 줄에 현재 판에서 돌 2개를 두어 죽일 수 있는 상대 돌의 최대 갯수를 출력한다.

접근 방법 

DFS와 두번의 BFS를 활용하면 쉽게 풀 수 있는 문제였다.

알고리즘은 크게 아래의 두 단계로 나뉜다. 

1) 빈 칸들 중에서 "내 돌 두개를 놓을 좌표 두개" 를 고르는 모든 경우를 구한다. (DFS)

2) 내 돌 두개를 놓았으면, 그 상태에서 내 돌에 둘러쌓여 죽는 상대 돌의 개수를 구한다. -> 이 개수를 비교해서 최대 값을 구한다.

그럼 2)에서 죽게되는 상대 돌의 개수를 어떻게 구할까?

먼저, BFS를 이용해서 상대 돌의 그룹들을 구한다. 각 그룹의 시작 좌표를 "partnerGroup_StartLoc"  벡터에 저장한다. 

그 후, 이 벡터에 저장된 [상대 돌 그룹의 시작 좌표] 에서  한번 더 BFS를 돌린다. BFS는 아래와 같이 동작한다.

//어느 그룹이 빈틈없이 에워싸였다는 것 <=> 그 그룹 내에 빈 칸과 인접해있는 돌이 하나도 없다는 것
int getKilled(){
    int ret = 0;

    int v[20][20];
    
    for (int i = 0; i < partnerGroup_StartLoc.size(); i++)
    { //BFS로 흰색 그룹들 모두 검사. 둘러 쌓여있는 그룹에서 죽는 돌 개수 세기 

        queue<pair<int,int>> tmpQue;
        
        memset(v, 0, sizeof(v));
        int r = partnerGroup_StartLoc[i].first;
        int c = partnerGroup_StartLoc[i].second;

        v[r][c] = 1;
        int killedCnt = 1;
        bool isContinue = true;

        tmpQue.push(make_pair(r,c));
        while(!tmpQue.empty()){     

            int cr = tmpQue.front().first;
            int cc = tmpQue.front().second;
            tmpQue.pop();

            for (int k = 0; k < 4; k++)
            {
                int nr = cr + dr[k];
                int nc = cc + dc[k];
                if (nr < 0 || nr >= N || nc < 0 || nc >= M || v[nr][nc]==1) continue;

                //빈칸이랑 인접했으면 그 그룹은 에워쌓이지 않은 것. 
                if(map[nr][nc] == 0){
                    isContinue = false;
                    break;
                }
                //백돌끼리 인접한 것이므로 큐에 담고 계속해서 검사 진행한다.
                if(map[nr][nc] == 2){
                    v[nr][nc] = 1;
                    killedCnt++;
                    tmpQue.push(make_pair(nr,nc));
                }
                    
            }
            if(!isContinue) break;
        }
        if(isContinue){ //모두 둘러 쌓인 경우에만 합해준다. 
            ret += killedCnt;
        }
    }
    return ret;
}

- next좌표가 2이면 v[][]에 방문했음을 표시한다.

- next좌표가 0이면 빈칸이므로 해당 그룹은 내 돌에 의해 둘러 쌓여있지 않은 그룹이므로 패스하고 다음 그룹을 검사한다.

- next좌표가 1이면 큐에 담지 않고 계속해서 큐에 담긴 좌표들 검사를 진행한다.

그 그룹이 모두 빈칸이랑 한번도 인접한 적이 없다면 죽은 돌의 개수를 합한다.

모든 그룹을 검사해서 죽은돌의 개수 합을 리턴하며, 리턴된 값들 중 최대값을 구해서 출력하면 된다..

전체 코드는 아래와 같다.

#include <iostream>
#include <queue>
#include <utility>
#include <vector>
#include <string.h>
using namespace std;

int map[20][20];
int visited[20][20];
int N, M;
//위 오 아 왼
int dr[4] = {-1, 0, 1, 0};
int dc[4] = {0, 1, 0, -1};
int answer = 0;

vector<pair<int,int>> spaceVec;
vector<pair<int, int>> partnerGroup_StartLoc;
vector<int> pickedIdxVec;

int picked[400] = {0,};

//상대편 돌들의 그룹 표시하기 위한 함수 
void BFS(int r, int c){

    visited[r][c] = 1;
    queue<pair<int,int>> que;
    que.push(make_pair(r,c));

    while(!que.empty()){

        int cr = que.front().first;
        int cc = que.front().second;
        que.pop();

        for(int i = 0; i<4; i++){
            int nr = cr + dr[i];
            int nc = cc + dc[i];

            if(nr<0 || nr>=N || nc<0 || nc>=M || visited[nr][nc] == 1 || map[nr][nc] != 2) continue;

            visited[nr][nc] = 1;
            que.push(make_pair(nr, nc));
        }


    }

}



//어느 그룹이 빈틈없이 에워싸였다는 것 <=> 그 그룹 내에 빈 칸과 인접해있는 돌이 하나도 없다는 것
int getKilled(){
    int ret = 0;

    int v[20][20];
    
    for (int i = 0; i < partnerGroup_StartLoc.size(); i++)
    { //BFS로 흰색 그룹들 모두 검사. 둘러 쌓여있는 그룹에서 죽는 돌 개수 세기 

        queue<pair<int,int>> tmpQue;
        
        memset(v, 0, sizeof(v));
        int r = partnerGroup_StartLoc[i].first;
        int c = partnerGroup_StartLoc[i].second;

        v[r][c] = 1;
        int killedCnt = 1;
        bool isContinue = true;

        tmpQue.push(make_pair(r,c));
        while(!tmpQue.empty()){     

            int cr = tmpQue.front().first;
            int cc = tmpQue.front().second;
            tmpQue.pop();

            for (int k = 0; k < 4; k++)
            {
                int nr = cr + dr[k];
                int nc = cc + dc[k];
                if (nr < 0 || nr >= N || nc < 0 || nc >= M || v[nr][nc]==1) continue;

                //빈칸이랑 인접했으면 그 그룹은 에워쌓이지 않은 것. 
                if(map[nr][nc] == 0){
                    isContinue = false;
                    break;
                }
                //백돌끼리 인접한 것이므로 큐에 담고 계속해서 검사 진행한다.
                if(map[nr][nc] == 2){
                    v[nr][nc] = 1;
                    killedCnt++;
                    tmpQue.push(make_pair(nr,nc));
                }
                    
            }
            if(!isContinue) break;
        }
        if(isContinue){ //모두 둘러 쌓인 경우에만 합해준다. 
            ret += killedCnt;
        }
    }
    return ret;
}

void pickDFS(int toPick){
    if(toPick==0)
    { //돌 놓을 위치 2개 골랐으면, 그 상태에서 죽일 수 있는 상대 돌의 최대 갯수 구하기
        int r1 = spaceVec[pickedIdxVec[0]].first;
        int c1 = spaceVec[pickedIdxVec[0]].second;

        int r2 = spaceVec[pickedIdxVec[1]].first;
        int c2 = spaceVec[pickedIdxVec[1]].second;

        map[r1][c1] = 1; map[r2][c2] = 1;   //내 돌 놓기
        int sum = getKilled();
        answer = max(answer, sum);
        map[r1][c1] = 0; map[r2][c2] = 0;   //원상 복구
        return;
    }

    for(int i = 0; i<spaceVec.size(); i++){
        if(picked[i] == 0){
            picked[i] = 1;
            pickedIdxVec.push_back(i);
            pickDFS(toPick-1);
            pickedIdxVec.pop_back();
            picked[i] = 0;
        }
    }
}

int main()
{
    
    cin >> N >> M;
    for(int i = 0; i<N; i++){
        for(int j = 0; j<M; j++){
            cin >> map[i][j];
            if(map[i][j] == 0) spaceVec.push_back(make_pair(i,j));
        }
    }


    //상대편 그룹의 시작 위치 찾기
    memset(visited, 0, sizeof(visited));
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < M; j++)
        {
            if(map[i][j] == 2 && visited[i][j] == 0){
                partnerGroup_StartLoc.push_back(make_pair(i,j));
                BFS(i,j);
            }
        }
    }

    //빈공간에서 내 돌 놓을 곳 2개 고르기 -> 완전탐색
    pickDFS(2);
    cout << answer;

    return 0;
}

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

문제

십자가는 가운데에 '*'가 있고, 상하좌우 방향으로 모두 같은 길이의 '*'가 있는 모양이다. 십자가의 크기는 가운데를 중심으로 상하좌우 방향으로 있는 '*'의 개수이다. 십자가의 크기는 0보다 크거나 같아야 한다.

아래 그림은 크기가 0, 1, 2, 3인 십자가이고, 빈 칸은 '.'이다.

십자가의 넓이는 포함된 '*'의 개수이다. 크기가 0, 1, 2, 3인 십자가의 넓이는 1, 5, 9, 13이다.

크기가 N×M이고, '.'과 '#'로 이루어진 격자판이 주어진다. 격자판에 두 개의 십자가를 겹치지 않게 놓으려고 한다. 십자가는 '#'가 있는 칸에만 놓을 수 있다. 놓인 십자가 넓이의 곱의 최댓값을 구해보자.

입력

첫째 줄에 격자판의 크기 N, M (2 ≤ N, M ≤ 15)이 주어진다. 둘째 줄부터 N개의 줄에 격자판의 상태가 주어진다. 항상 두 개의 십자가를 놓을 수 있는 경우만 입력으로 주어진다.

출력

첫째 줄에 놓은 십자가 넓이의 곱의 최댓값을 출력한다.

접근 방법

첫번째 십자가의 가능한 크기가 0부터 max라고 했을 때,

모든 경우에 대해, 두번째 십자가의 가능한 크기를 모두 구해서 최대 넓이를 구하는 방식이다. 

처음에는,

십자가 중심 2개를 (r1, c1), (r2, c2) 라고 했을 때, DFS를 이용하여 모든 (r1, c1), (r2, c2) 의 조합을 구했다. 

그 후, 십자가 두개의 크기를 각각 1씩 증가시켜 나가면서 넓이를 구했다.

그러나 이 방식은 완전탐색이 아니다.

왜냐하면 1번 십자가의 크기를 1 증가시킨 후 -> 1번과 2번 십자가가 겹치지 않는 한에서 2번 십자가의 크기를 1 증가한 뒤 넓이를 계산했기 때문이다. 완전탐색을 하려면 반대 순으로도 넓이를 각 경우에 대해 계산해야하며, 중간에도 계산을 한번 더 해야한다. 

즉,  아래와 같이 여러번의 계산이 필요한 것이다. 

1번 십자가 크기 1 증가 -> 넓이 계산 -> 2번 십자가 크기 1 증가 -> 넓이 계산
2번 십자가 크기 1 증가 -> 넓이 계산 -> 1번 십자가 크기 1 증가 -> 넓이 계산

또한, 아래 링크의 테스트케이스는 4달 전에 추가된 데이터로, 이 경우도 주의해야한다. 

이렇게 두가지 고려할 점이 있지만 

 첫번째 십자가의 가능한 크기가 0부터 max라고 했을 때,
모든 경우에 대해, 두번째 십자가의 가능한 크기를 모두 구해서 최대 넓이를 구하는 방식이다. 

이 방식으로 그냥 모든 가능한 경우를 완전탐색하면 보다 단순하게 해결 가능하다.

#include <iostream>
#include <vector>
#include <utility>
#include <string.h>
#include <algorithm>
using namespace std;

int N, M;
char map[15][15];
int answer = 0;

//위 오 아 왼
int dr[4] = {-1, 0, 1, 0};
int dc[4] = {0, 1, 0, -1};

//(r,c)가 중심일 때, 가능한 십자가의 최대 크기
int getSize(int r, int c){  
    int ret = 0;
    while(1){
        bool flag = true;
        for(int i = 0; i<4; i++){
            int nr = r + dr[i]*ret;
            int nc = c + dc[i]*ret;
            if(nr<0 || nc<0 || nr>=N || nc>=M || map[nr][nc] != '#'){
                flag = false;
                break;
            }
        }
        if(flag) ret++;
        else break;
    }
    return ret - 1; //ret가 0부터 시작하므로, 처음 통과하면 ret=1이 되는데 이때 십자가의 크기는 0임 ('*' 한개짜리)
}

//중심이 (r,c)이고 크기가 K인 십자가를 만들거나(val='#') 십자가 원상복구(val='.')
void make_cross(int r, int c, int k, int val){ 
    for(int i = 0; i<=k; i++){
        for(int j = 0; j<4; j++){
            int nr = r + dr[j]*i;
            int nc = c + dc[j]*i;
            map[nr][nc] = val;
        }
    }
}

int main()
{
    cin >> N >> M;
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < M; j++)
        {
            cin >> map[i][j];
        }
    }


    for(int i = 0; i<N; i++){
        for(int j = 0; j<M; j++){
            if(map[i][j] == '#'){
                int step1 = getSize(i,j);
                for (int k = 0; k <= step1; k++)    //첫번째 십자가 크기 1부터 max까지, 
                {
                    make_cross(i,j,k,'*');  //첫번째 십자가 표시

                    for(int r = 0; r<N; r++){
                        for(int c=0; c<M; c++){
                            if(map[r][c] == '#'){
                                int step2 = getSize(r,c); //각 크기에 대해 두번째 십자가 크기 구하기
                                int width1 = 4*k + 1;
                                int width2 = 4*step2 + 1;
                                answer = max(answer, width1*width2);
                            }
                        }
                    }
                    make_cross(i,j, k, '#');    //첫번째 십자가 원상복구


                }
            } 
        
            
        }
    }
    
   
    cout << answer;

    return 0;
}

(참고 : https://www.acmicpc.net/source/30665990)

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

문제

일반적으로 잠수함 엔진이 작동할 때에 나오는 소리는 잠수함의 종류에 따라서 다르다고 한다.

우리는 물속에서 들리는 소리의 패턴을 듣고서 그 소리가 특정한 잠수함에서 나오는 소리인지 아닌지를 알아내려고 한다. 이 문제에서는 잠수함의 소리가 두 종류의 단위 소리의 연속으로 이루어져 있고, 그 단위 소리를 각각 0과 1로 표시한다.

또, 한 특정한 소리의 반복은 ~로 표시한다. 예를 들어 x~는 x가 한번 이상 반복되는 모든 소리의 집합을 말하고, (xyz)~는 괄호 안에 있는 xyz로 표현된 소리가 한번 이상 반복되는 모든 소리의 집합을 말한다. 다음의 예를 보라.

• 1~ = {1, 11, 111, 1111, ..., 1...1, ...}
• (01)~ = {01, 0101, 010101, 01010101. ...}
• (1001)~ = {1001, 10011001, ..., 100110011001...1001, ...}
• 10~11 = {1011, 10011, 100011, ..., 1000...011, ...}
• (10~1)~ = {101, 1001, 10001, 100001, ...1011001, ...100110110001101, ...}

​그리고 (x|y)는 x또는 y중에서 아무거나 하나만을 선택해서 만든 소리의 집합, 즉 집합{x, y}를 의미한다. 예를 들면(1001|0101)은 집합으로 {1001, 0101}을 의미한다. 따라서 (0|1)~은 0과 1로 이루어진 모든 스트링의 집합, 즉 모든 소리의 집합을 말한다. 또 한 예를 보면 (100|11)~은 100과 11을 마음대로 섞어서 만들 수 있는 모든 소리의 집합을 의미한다. 즉 (100|11)~에 해당하는 스트링을 집합으로 나타내면 {100, 11, 10011, 100100100, 1110011, ...}이 된다. 우리가 식별하고자 하는 잠수함의 엔진소리의 패턴은 다음과 같다.

(100~1~|01)~

여기에 속하는 소리의 예를 들어보면, 1001, 01, 100001, 010101, 1000001110101, 1001110101, 0101010101, 10010110000001111101, 01010101011000111, 10000111001111, ...이다.

다시 말해서 이것은 100~1~과 01을 임의로 섞어서 만들 수 있는 모든 스트링의 집합을 나타낸다.

입력으로 0과 1로 구성된 스트링이 주어질 때, 이 스트링이 앞에서 기술된 잠수함의 엔진소리인지 아닌지를 판별하는 프로그램을 작성하라.

접근 방법

주어진 식은 (100~1~|01)~ 이다.

- part A : 100~

- part B : 1~

 - part C = 01

이라고 하자. 

그 후, next State = cur State + next Char 형식에 맞춰서 나올 수 있는 모든 경우를 계산해보면 다음과 같다.

이렇게 구한 값은 unordered_map<string, vector<string>> umap에 넣어주면 된다.

이때 주의할 점은 value에 해당하는 vector에 nextState값을 넣을 때 인덱스를 고려해서 넣어야한다. 즉, next Char 이 0이면 vector의 0번째 인덱스 [0]에 넣어주고, 1이면 1번째 인덱스[1]에 넣어준다. 그래야 입력된 문자열을 한 글자씩 따라가면서 주어진 형식을 어긋나지 않는지 검사할 수 있다.

그렇게 입력된 문자열을 다 검사한 뒤에, state의 값을 검사한다. 이때 잠수함 엔진소리라면 

case 1) part A -> part B에서 끝나거나

case 2) part C 에서 끝나야 한다. 

case 1)은 "100~1" 와 "100~1~"이 해당되고, case 2)는 "01"이 해당된다.

마지막 state 값이 이 세가지 중 하나라면 잠수함 엔진소리가 맞고, 그 외는 엔진소리가 아니다.

//
//  BF_BOJ2671_잠수함식별.cpp
//  Coding_Test_Practice
//
//  Created by 김난영 on 2021/07/06.
//  Copyright © 2021 KimNanyoung. All rights reserved.
//


#include <iostream>
#include <string>
#include <unordered_map>
#include <vector>
using namespace std;

int main(){
    
    string str;
    cin >> str;
    
    unordered_map<string, vector<string>> umap;
    
    umap["init"] = {"0","1"};
    umap["0"] = {"X", "01"};
    umap["1"] = {"10", "X"};
    umap["01"] = {"0", "1"};
    umap["10"] = {"100", "X"};
    umap["100"] = {"100~", "100~1"};
    umap["100~"] = {"100~", "100~1"};
    umap["100~1"] = {"0", "100~1~"};
    umap["100~1~"] = {"10 or 0", "100~1~"};
    umap["10 or 0"] = {"100", "01"};
    
    string state = "init";
    for(int i = 0; i<str.length(); i++){
        int nextChar = str[i] - '0';
        state = umap[state][nextChar];
        if(state == "X") break;
    }
    
    if(state == "100~1" || state == "100~1~" || state =="01") cout << "SUBMARINE";
    else cout << "NOISE";
    
    
    
    return 0;
}

(사실 <regex> 라이브러리를 활용하면 한 줄로 끝난다.)

참고  : (https://gglifer-cs.tistory.com/74)

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

문제

크기가 H×W인 모눈종이와 스티커 N개가 있다. i번째 스티커의 크기는 Ri×Ci이다. 모눈종이는 크기가 1×1인 칸으로 나누어져 있으며, 간격 1을 두고 선이 그어져 있다.

오늘은 모눈종이에 스티커 2개를 붙이려고 한다. 스티커의 변은 격자의 선과 일치하게 붙여야 하고, 두 스티커가 서로 겹치면 안 된다. 단, 스티커가 접하는 것은 가능하다. 스티커를 90도 회전시키는 것은 가능하다. 스티커가 모눈종이를 벗어나는 것은 불가능하다.

두 스티커가 붙여진 넓이의 최댓값을 구해보자.

입력

첫째 줄에 모눈종이의 크기 H, W, 둘째 줄에 스티커의 수 N이 주어진다. 다음 N개의 줄에는 스티커의 크기 Ri, Ci가 주어진다.

출력

첫째 줄에 두 스티커가 붙여진 넓이의 최댓값을 출력한다. 두 스티커를 붙일 수 없는 경우에는 0을 출력한다.

제한

• 1 ≤ H, W, N ≤ 100
• 1 ≤ Ri, Ci ≤ 100

접근 방법

N개의 스티커 중 DFS 함수를 이용해 2개를 고른다. 이 때 중복 조합을 이용해 중복을 제거한다.

고른 2개의 스티커에 대해 총 4가지 경우를 따져서 스티커를 붙일 수 있는지 검사해야한다.

1) 둘 다 그대로

2) 1번 스티커만 회전

3) 2번 스티커만 회전

4) 둘 다 회전

각 경우에 대해 위 아래로 붙였을 때와 좌우로 붙였을 때 모두 검사해서 하나라도 모눈종이 안에 들어온다면 스티커 두개 넓이를 계산한다.

import java.util.*;

class Pair16937{
	Integer h, w;
	public Pair16937(Integer _h, Integer _w) {
		this.h = _h;
		this.w = _w;
	}
	public Integer getHeight() {
		return this.h;
	}
	public Integer getWidth() {
		return this.w;
	}
}

public class BF_BOJ16937_두스티커 {
	
	static int H, W, N;
	static int[] visited = new int[100];
	static ArrayList<Pair16937> pairList = new ArrayList<Pair16937>();
	static ArrayList<Pair16937> tmpList = new ArrayList<Pair16937>();
	static int maxi = 0;
	
	static boolean chkHeight(int h1, int w1, int h2, int w2) {		//위 아래로 붙였을 때 
		if(h1+h2 > H || Math.max(w1, w2) > W) return false;
		else return true;
	}
	static boolean chkWidth(int h1, int w1, int h2, int w2) {		//양옆으로 붙였을 때 
		if(Math.max(h1, h2) > H || w1 + w2 > W) return false;
		else return true;
	}
	
	static boolean chkHW(int h1, int w1, int h2, int w2) {
		if(chkHeight(h1,w1,h2,w2)==true || chkWidth(h1,w1,h2,w2)==true) return true;
		else return false;
	}
	
	
	static void DFS(int toPick, int start) {
		
		if(toPick==0) {
			int h1 = tmpList.get(0).getHeight();
			int w1 = tmpList.get(0).getWidth();
			
			int h2 = tmpList.get(1).getHeight();
			int w2 = tmpList.get(1).getWidth();
			
			//1번 그대로, 2번 그대로 
			boolean chk = false;
			if(chkHW(h1,w1,h2,w2) == true) {	
				int area = h1*w1 + h2*w2;
				if(maxi<area) maxi = area;
				chk = true;
			}
			else {
				for(int i = 0; i<3; i++) {
					int a,b,c,d;
					if(i==0) {				//1번 회전, 2번 그대로
						a = w1; b = h1;
						c = h2; d = w2;
					}
					else if(i==1) {			//1번 그대로, 2번 회전
						a = h1; b = w1;
						c = w2; d = h2;
					}
					else {					//1번 회전, 2번 회전 
						a = w1; b = h1;
						c = w2; d = h2;
					}
					if(chkHW(a,b,c,d)==true) {
						chk = true;
						int area = h1*w1 + h2*w2;
						if(maxi<area) maxi = area;
						return;
					}
				}
			}
			
			return;
		}
		
		for(int i = start; i<pairList.size(); i++) {
			
			if(visited[i]==0) {
				visited[i] = 1;
				tmpList.add(pairList.get(i));
				DFS(toPick-1, i);
				tmpList.remove(tmpList.size()-1);
				visited[i] = 0;
			}
		}
	}
	
	
	public static void main(String[] args) {
		
		Scanner sc = new Scanner(System.in);
		H = sc.nextInt();
		W = sc.nextInt();
		N = sc.nextInt();
		for(int i = 0; i<N; i++) {
			int h = sc.nextInt();
			int w = sc.nextInt();
			pairList.add(new Pair16937(h,w));
		}
		
		DFS(2,0);
		
		System.out.print(maxi);
	}
}

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

문제

수빈이는 TV를 보고 있다. 수빈이는 채널을 돌리려고 했지만, 버튼을 너무 세게 누르는 바람에, 일부 숫자 버튼이 고장났다.

리모컨에는 버튼이 0부터 9까지 숫자, +와 -가 있다. +를 누르면 현재 보고있는 채널에서 +1된 채널로 이동하고, -를 누르면 -1된 채널로 이동한다. 채널 0에서 -를 누른 경우에는 채널이 변하지 않고, 채널은 무한대 만큼 있다.

수빈이가 지금 이동하려고 하는 채널은 N이다. 어떤 버튼이 고장났는지 주어졌을 때, 채널 N으로 이동하기 위해서 버튼을 최소 몇 번 눌러야하는지 구하는 프로그램을 작성하시오. 

수빈이가 지금 보고 있는 채널은 100번이다.

입력

첫째 줄에 수빈이가 이동하려고 하는 채널 N (0 ≤ N ≤ 500,000)이 주어진다.  둘째 줄에는 고장난 버튼의 개수 M (0 ≤ M ≤ 10)이 주어진다. 고장난 버튼이 있는 경우에는 셋째 줄에는 고장난 버튼이 주어지며, 같은 버튼이 여러 번 주어지는 경우는 없다.

출력

첫째 줄에 채널 N으로 이동하기 위해 버튼을 최소 몇 번 눌러야 하는지를 출력한다.

접근 방법

간단해 보이지만 의외로 복잡한 문제였다.

누군가 친절하게 올려주신 반례를 사용해서 풀 수 있었다.

* 반례 모음(https://www.acmicpc.net/board/view/46120)

1555
8
0 1 3 4 5 6 7 9

를 예로 들어보자. 결론부터 말하면 답은 670이고 888을 누른 뒤(3번) 667번(1555-888) -버튼을 누를 때가 최소로 버튼을 눌러서 1555를 만드는 경우이다. 나는 아래의 방법으로 생각해서 틀렸다. 

처음에는 한 자리수씩 따져서 고장나지 않은 버튼으로 누를 수 있는 숫자를 만든 후 더 적게 +/-를 눌러서 N에 도달하는 경우일 때 해당 숫자를 저장했다.

즉, 1은 고장난 버튼이니 

case1) 2부터 9까지의 수 중에 고장나지 않은 버튼 중 최소 수를 구한다. -> 2

case2) 0부터 0까지 수 중에 고장나지 않은 버튼 중 최대 수를 구한다. -> 없음

2를 저장한다.

그 다음은 5인데, 5도 고장난 버튼이니

case1) 6부터 9까지의 수 중에 고장나지 않은 버튼 중 최소 수를 구한다. -> 8 -> 28 -15 = 13

case2) 4부터 0까지 수 중에 고장나지 않은 버튼 중 최대 수를 구한다. -> 2 -> 22 - 15 = 7

13>7로 더 작은 case2) 의 2를 앞에서 저장한 2 뒤에 붙여 22를 저장한다. 

그래서 결국 2222를 만든 후(2버튼 4번 누름) 667번(2222-1555)을 -버튼을 눌러서 1555를 만들 수 있다. 이 때 답은 4+667 = 671이 된다. 

결국 완전 탐색으로 풀어주었다. i = 0부터 999999까지 돌면서 (N의 최대값이 500,000이므로 6자리수 중 최대 값까지 검사한다) 검사한다.

만약 고장난 버튼 때문에 i를 바로 누르지 못하면 다음 수를 검사한다.

아니라면 i의 자리수 + |N-i| 를 구하며 이 값의 최소값을 저장한다.

import java.util.*;

public class BF_BOJ1107_리모컨 {

	public static void main(String[] args) {
		// TODO Auto-generated method stub

		int N, M;
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt();
		M = sc.nextInt();
		
		ArrayList<Integer> troubleButton = new ArrayList<Integer>();
		
		
		for(int i = 0; i<M; i++) {	//고장난 버튼 
			int but = sc.nextInt();
			troubleButton.add(but);
		
		}
		
		int ans = Math.abs(100-N);			//+, - 버튼으로만 움직였을 때 
		
		int mini = 987654321;
		int cnt = 0;
		
		for(int i = 0; i<=999999; i++) {		//완전 탐색 
			
			String str = String.valueOf(i);
			boolean chk = true;
			for(int k = 0; k<str.length(); k++) {
				if(troubleButton.contains(str.charAt(k)-'0')) {		//고장난 버튼 때문에 바로 i 못 누르면 스킵 
					chk=false; break;
				}
			}
			if(chk==false) continue;
			
			cnt = str.length() + Math.abs(i-N);	//고장난 버튼 없어서 바로 i를 누를 수 있으면 i 누르고 +/- 눌러서 이동  
			
			
			if(cnt < mini) {
				mini = cnt;
			}
	
		}
		
		if(mini < ans) ans = mini;
		System.out.println(ans);

		
	}

}

문제 링크 : www.acmicpc.net/problem/15686

문제

크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸, 왼쪽에서부터 c번째 칸을 의미한다. r과 c는 1부터 시작한다.

이 도시에 사는 사람들은 치킨을 매우 좋아한다. 따라서, 사람들은 "치킨 거리"라는 말을 주로 사용한다. 치킨 거리는 집과 가장 가까운 치킨집 사이의 거리이다. 즉, 치킨 거리는 집을 기준으로 정해지며, 각각의 집은 치킨 거리를 가지고 있다. 도시의 치킨 거리는 모든 집의 치킨 거리의 합이다.

임의의 두 칸 (r1, c1)과 (r2, c2) 사이의 거리는 |r1-r2| + |c1-c2|로 구한다.

예를 들어, 아래와 같은 지도를 갖는 도시를 살펴보자.

0은 빈 칸, 1은 집, 2는 치킨집이다.

(2, 1)에 있는 집과 (1, 2)에 있는 치킨집과의 거리는 |2-1| + |1-2| = 2, (5, 5)에 있는 치킨집과의 거리는 |2-5| + |1-5| = 7이다. 따라서, (2, 1)에 있는 집의 치킨 거리는 2이다.

(5, 4)에 있는 집과 (1, 2)에 있는 치킨집과의 거리는 |5-1| + |4-2| = 6, (5, 5)에 있는 치킨집과의 거리는 |5-5| + |4-5| = 1이다. 따라서, (5, 4)에 있는 집의 치킨 거리는 1이다.

이 도시에 있는 치킨집은 모두 같은 프랜차이즈이다. 프렌차이즈 본사에서는 수익을 증가시키기 위해 일부 치킨집을 폐업시키려고 한다. 오랜 연구 끝에 이 도시에서 가장 수익을 많이 낼 수 있는  치킨집의 개수는 최대 M개라는 사실을 알아내었다.

도시에 있는 치킨집 중에서 최대 M개를 고르고, 나머지 치킨집은 모두 폐업시켜야 한다. 어떻게 고르면, 도시의 치킨 거리가 가장 작게 될지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N(2 ≤ N ≤ 50)과 M(1 ≤ M ≤ 13)이 주어진다.

둘째 줄부터 N개의 줄에는 도시의 정보가 주어진다.

도시의 정보는 0, 1, 2로 이루어져 있고, 0은 빈 칸, 1은 집, 2는 치킨집을 의미한다. 집의 개수는 2N개를 넘지 않으며, 적어도 1개는 존재한다. 치킨집의 개수는 M보다 크거나 같고, 13보다 작거나 같다.

출력

첫째 줄에 폐업시키지 않을 치킨집을 최대 M개를 골랐을 때, 도시의 치킨 거리의 최솟값을 출력한다.

접근 방법

1) 기본 DFS + 기본 BFS -> 시간 초과

처음에는 DFS로 치킨 집 중 M개를 선택하고, 선택이 완료되면 BFS로 각 집에서 치킨집까지 최소 거리를 구했다. 그랬더니 답은 제대로 나왔지만 시간 초과가 떴다.

2) 기본 DFS + BFS 사용x -> 시간 초과

M의 최대가 13밖에 안되니 BFS 대신 직접 각 집에서 치킨집까지 거리를 abs()를 이용해서 구했다.

3) 중복조합으로 DFS 개선 + BFS 사용x -> 통과

치킨 집을 2개 선택한다 했을 때, <1번, 2번> 이나 <2번, 1번>이나 같으므로 중복 조합을 이용했다.

//
//  BF_BOJ15686_치킨배달.cpp
//  Coding_Test_Practice
//
//  Created by 김난영 on 2021/04/11.
//  Copyright © 2021 KimNanyoung. All rights reserved.
//
#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>
#include <string.h>
#include <queue>
#include <cmath>
using namespace std;

int N, M;

int map[51][51];
int fromStart[51][51];
int newMap[51][51];
vector<pair<int,int>> homeVec;       //1
vector<pair<int,int>> chickenVec;   //2
int visited[100] = {0};
vector<pair<int,int>> pickedChick;   //2중 M개 선택

//위 오 아 왼
int dr[4] = {-1,0,1,0};
int dc[4] = {0,1,0,-1};
int mini = 100000000;
int answer =100000000;


void pickChickDFS(int toPick, int start){

    if(toPick==0){
        
        int sum=0;
        //각 집에서 pickChick까지의 거리들 중 최소값들의 합
        for(int i = 0; i<homeVec.size();i++){
            mini = 100000000;
            
            for(int j = 0; j<pickedChick.size(); j++){
                int dis = abs(homeVec[i].first-pickedChick[j].first)
                + abs(homeVec[i].second - pickedChick[j].second);
                
                if(mini>dis) mini = dis;
            }
            sum+=mini;
            if(sum>answer) return;
        }
        
        if(answer>sum) answer = sum;
        return;
    }
    
    for(int i = start; i<chickenVec.size(); i++){
        if(visited[i]==0){
            visited[i] = 1;
            pickedChick.push_back(chickenVec[i]);
            pickChickDFS(toPick-1, i);
            pickedChick.pop_back();
            visited[i] = 0;
        }
    }
}


int main(){
    cin >> N >> M;
    
    for(int i = 1; i<=N; i++){
        for(int j = 1; j<=N; j++){
            cin >> map[i][j];
            if(map[i][j]==1){   homeVec.push_back(make_pair(i,j)); }
            if(map[i][j]==2){   chickenVec.push_back(make_pair(i,j)); }
        }
    }
    
    pickChickDFS(M, 0);
    cout << answer;
    
    return 0;
}

문제 링크 : www.acmicpc.net/problem/16943

문제

두 정수 A와 B가 있을 때, A에 포함된 숫자의 순서를 섞어서 새로운 수 C를 만들려고 한다. 즉, C는 A의 순열 중 하나가 되어야 한다. 

가능한 C 중에서 B보다 작으면서, 가장 큰 값을 구해보자. C는 0으로 시작하면 안 된다.

입력

첫째 줄에 두 정수 A와 B가 주어진다.

출력

B보다 작거나 같은 C중에서 가장 큰 값을 출력한다. 그러한 C가 없는 경우에는 -1을 출력한다.

접근 방법

정수 A를 string으로 형변환 한 뒤, 각 문자를 vector에 넣고 DFS를 돌려서 완전 탐색을 해 주었다. 

DFS를 돌면서 vector안의 각 요소를 str에 push_back()으로 붙이고 pop_back()으로 빼주었다.

A의 자리수만큼 수를 만들었으면 정수형으로 다시 바꾼뒤 문제의 조건을 만족하는지 확인한다.

//
//  BF_BOJ16943_숫자재배치.cpp
//  Coding_Test_Practice
//
//  Created by 김난영 on 2021/04/05.
//  Copyright © 2021 KimNanyoung. All rights reserved.
//

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

int visited[10] = {0};
vector<char> vec;
int A,B;
string strB;
int maxi = 0;
int answer = 0;
void DFS(int toPick, string str){
    
    if(toPick==0){
        int num = stoi(str);

        if(num!=A && num<B){        //B보다 작으면서
            if(maxi<num) {          //그 중 가장 큰 값
                maxi = num;
                answer = num;
            }
        }
    }
    
    for(int i = 0; i<vec.size(); i++){
        
        if(visited[i]==0){
            if(str.length()==0 && vec[i]=='0') continue;        //처음 0이 오면 안됨
            visited[i] = 1;
            str.push_back(vec[i]);
            DFS(toPick-1, str);
            str.pop_back();
            visited[i] = 0;
        }
    }
}


int main(){
    
    cin >> A >> B;
    
    string strA = to_string(A);
    string strB = to_string(B);
    int nLen = (int)strA.length();
    
    for(int i = 0; i<nLen; i++){
        vec.push_back(strA[i]);
    }
    
    DFS(nLen, "");
    if(answer==0) answer=-1;
    cout << answer ;
    
    return 0;
}