개발 블로그

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

문제

수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 500,000)에 있고, 동생은 점 K(0 ≤ K ≤ 500,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다. 동생은 항상 걷기만 한다. 동생은 항상 매 초마다 이동을 하며, 이동은 가속이 붙는다. 동생이 이동하는 거리는 이전에 이동한 거리보다 1을 더한 만큼 이동한다. 즉, 동생의 처음 위치는 K, 1초가 지난 후 위치는 K+1, 2초가 지난 후 위치는 K+1+2, 3초가 지난 후의 위치는 K+1+2+3이다.

수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오. 동생을 찾는 위치는 정수 좌표이어야 하고, 수빈이가 0보다 작은 좌표로, 50만보다 큰 좌표로 이동하는 것은 불가능하다.

입력

첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어진다. N과 K는 정수이다.

출력

수빈이가 동생을 찾는 가장 빠른 시간을 출력한다. 수빈이가 동생을 찾을 수 없거나, 찾는 위치가 500,000을 넘는 경우에는 -1을 출력한다.

접근 방법

참고 : (https://imucoding.tistory.com/736)

수빈이가 +1, -1로 간다는 점을 주의하자. 즉 다시 제자리로 돌아갈 수 있다! 

링크에서의 방법 말고 그냥 보통 BFS 방식으로 풀어서 중복으로 해당 지점에 방문하는 경우에 대해 처리를 해주지 않으면 메모리 초과가 난다. 동생의 위치는 계속해서 증가하므로 visit 배열에 "해당 지점에 도착한 최초 시간"을 저장함으로써 최초 시간 이후에 해당 지점에 도착한 경우에는 continue로 처리해준다. 

//
//  BFS_BOJ17071_숨바꼭질5.cpp
//  Coding_Test_Practice
//
//  Created by 김난영 on 2021/05/25.
//  Copyright © 2021 KimNanyoung. All rights reserved.
//

#include <iostream>
#include <queue>
#include <utility>
#include <string.h>

using namespace std;


int visited[2][500001];

bool chk(int loc){
    if(0<=loc && loc <= 500000) return true;
    else return false;
}

int main(){
    
    int N, K;
    cin>> N >> K;

    

    queue<pair<int,int>> que;
    que.push(make_pair(N,0));
    visited[0][N] = 0;      //첫 시작 위치는 0초만에 도달
    memset(visited, -1, sizeof(visited));
    
    while(!que.empty()){
    
        int subinLoc = que.front().first;
        int subinTime = que.front().second;
        que.pop();
          
        if(chk(subinLoc)== false) continue;
        if(visited[subinTime%2][subinLoc]!=-1) continue;
        
        visited[subinTime%2][subinLoc] = subinTime; //해당 위치에 최소 몇초만에 도달했는지 저장     
        
        que.push(make_pair(subinLoc-1, subinTime+1));
        que.push(make_pair(subinLoc+1, subinTime+1));
        que.push(make_pair(subinLoc*2, subinTime+1));
    }
    
    bool flag = false;
    for(int i = 0; i<=500000; i++){
        int nextK = K + (i*(i+1))/2;
        if(nextK > 500000) break;
        if(visited[i%2][nextK] != -1 && visited[i%2][nextK] <= i) {
            cout << i << endl;
            flag = true;
            break;
        }
    }
    if(!flag) cout << -1 << endl;
    
    return 0;
}

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

문제

폴란드 왕자 구사과는 다음과 같은 수를 좋아한다.

• 0과 1로만 이루어져 있어야 한다.
• 1이 적어도 하나 있어야 한다.
• 수의 길이가 100 이하이다.
• 수가 0으로 시작하지 않는다.

예를 들어, 101은 구사과가 좋아하는 수이다.

자연수 N이 주어졌을 때, N의 배수 중에서 구사과가 좋아하는 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수 T(T < 1,000)가 주어진다.

둘째 줄부터 T개의 줄에는 자연수 N이 한 줄에 하나씩 주어진다. N은 20,000보다 작거나 같은 자연수이다.

출력

각각의 테스트 케이스마다 N의 배수이면서, 구사과가 좋아하는 수를 아무거나 출력한다. 만약, 그러한 수가 없다면 BRAK을 출력한다.

접근 방법

N의 배수가 최대 100자리 까지 나올 수 있기 때문에 무작정 0과 1을 붙여가면서 N으로 나눠지는지 확인하면 안 된다. (오버플로우) 

어떤 수 x 가 N의 배수인지 확인하려면 (x mod N) 이 0인지 확인할 수도 있겠지만 x가 계속 커지는 걸 방지하기 위해 (x mod N) mod N이 0인지 확인하면 된다. modular 연산의 성질에 의해   (x mod N) 는 (x mod N) mod N와 같기 때문이다. 

그래서 x 대신 "현재의 수 cur에 0또는 1을 붙이고 N으로 나눈 나머지"를 고려하면 된다.  

cur = 1이라면 node[0]은 10%N. node[1] = 11%N이 된다. 

//자식 노드 2개, 가지치기, 0과 1을 붙일 수 있음
        int node[2];
        node[0] = (cur*10 + 0) % N;
        node[1] = (cur*10 + 1) % N;

그럼 어떻게 원래의 수를 기억할것인가?

매 depth 마다 0을 붙였는지 1을 붙였는지를 char 형으로 저장한 뒤에, depth가 마지막까지 내려왔을 때 거꾸로 올라가면서 어떤 수를 붙여왔는지 출력하면 된다. 

그럴려면 현재 노드에서 부모 노드를 타고 거꾸로 올라가려면 해당 노드의 부모 노드 번호를 알아야한다. 

arr[자식idx].first 에는 idx번째 자식노드의 부모 노드 번호를 저장하고,

arr[자식idx].second 에는 해당 depth에서 붙인 숫자를 char 형으로 저장한다. ('0' or '1')

다 저장하고 마지막에 0번째 자식부터 재귀 함수를 통해 거꾸로 올라가면서 arr[].second 를 출력한다. 이때, 0번째 자식부터 시작하는 이유는 (x mod N) mod N이 0이 되면서 그 0을 arr[]의 idx로 지정해 정보를 저장한 뒤, BFS() 함수를 종료했기 때문이다. 

//
//  BFS_BOJ8111_0과1.cpp
//  Coding_Test_Practice
//
//  Created by 김난영 on 2021/05/02. 05:27~06:10 / 06:24 / 06:40
//  Copyright © 2021 KimNanyoung. All rights reserved.
//

#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <utility>
#include <string.h>

using namespace std;
int N;
int visited[20001] = {0};
pair<int, char> arr[20001];

void BFS(){
    memset(visited, 0, sizeof(visited));
    queue<int> que;
    que.push(1);        //첫 글자는 0 안 됨
    
    //가장 첫 루트 노드
    arr[1].first = -1;   //부모 노드 번호 표시 (부모가 -1이면 루트 노드인 것)
    arr[1].second = '1'; //N의 배수는 1부터 시작하므로

    visited[1] = 1;
    
    
    while(!que.empty()){
        
        int cur = que.front();
        que.pop();
        
        
        //자식 노드 2개, 가지치기, 0과 1을 붙일 수 있음
        int node[2];
        node[0] = (cur*10 + 0) % N;
        node[1] = (cur*10 + 1) % N;
        
        for(int i = 0; i<2; i++){
            if(visited[node[i]]==1) continue;
            
            arr[node[i]].first = cur;   //node[i]의 부모 노드는 cur
            arr[node[i]].second = i + '0';      // 현재 수에서 어떤 수를 덧붙였는지 저장, i는 0또는 1인 정수. 여기에 '0' 더해서 char 형으로 변환
            
            if(node[i]==0) return;      //N으로 나눈 나머지가 0이므로 N의 배수 찾은 것
            
            visited[node[i]] = 1;       //방문했음을 표시
            que.push(node[i]);
            
            
        }
        
        
    }
    
}

void printReverse(int parent){
    if(parent==-1) return;      //부모 노드가 -1이면 루트 노드
    
    printReverse(arr[parent].first);
    cout << arr[parent].second;
    
}


int main(){
    
    
    int T; cin >> T;
    
    for(int test_case = 1; test_case<=T; test_case++){
        
         cin >> N;
        if(N==1) {
            cout << 1 << endl;      //1의 배수는 1이므로 바로 출력
            continue;
        }
        
        BFS();
        printReverse(0);            //arr[0] 부터 거꾸로 타고 올라감. 0부터 시작하는 이유는 N의 배수가 되면서 나머지가 0이 됐고 이를 인덱스로 해서 저장했기 때문에
        cout << endl;
        
        
    }
    
    return 0;
}

참고 : jaimemin.tistory.com/791

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

문제

영선이는 매우 기쁘기 때문에, 효빈이에게 스마일 이모티콘을 S개 보내려고 한다.

영선이는 이미 화면에 이모티콘 1개를 입력했다. 이제, 다음과 같은 3가지 연산만 사용해서 이모티콘을 S개 만들어 보려고 한다.

1. 화면에 있는 이모티콘을 모두 복사해서 클립보드에 저장한다.
2. 클립보드에 있는 모든 이모티콘을 화면에 붙여넣기 한다.
3. 화면에 있는 이모티콘 중 하나를 삭제한다.

모든 연산은 1초가 걸린다. 또, 클립보드에 이모티콘을 복사하면 이전에 클립보드에 있던 내용은 덮어쓰기가 된다. 클립보드가 비어있는 상태에는 붙여넣기를 할 수 없으며, 일부만 클립보드에 복사할 수는 없다. 또한, 클립보드에 있는 이모티콘 중 일부를 삭제할 수 없다. 화면에 이모티콘을 붙여넣기 하면, 클립보드에 있는 이모티콘의 개수가 화면에 추가된다.

영선이가 S개의 이모티콘을 화면에 만드는데 걸리는 시간의 최솟값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 S (2 ≤ S ≤ 1000) 가 주어진다.

출력

첫째 줄에 이모티콘을 S개 만들기 위해 필요한 시간의 최솟값을 출력한다.

접근 방법

처음 시작 조건(이모티콘 1개, 시간 0초, 클립보드 0개)에서 시작해서 각각 연산을 수행한 뒤 상태를 Queue에 push 한다.

여기서 주의할 점은 방문 여부를 체크하는 visit 배열이 이차원 배열이라는 것이다.

visit[i][j] 는 화면에 i개 이모티콘이 있고 클립보드에 j개 이모티콘이 있는 상태이다. 

처음에  '시간이 더 나중인게 이모티콘 글자 수가 더 큰 경우' 에는 ?

이라는 의문이 들었는데, 

whlie문 한 번 돌 때마다

if(s==S)인지 체크하고 / 1초씩 순차적으로 증가하기 때문에

if(s==S)이 만족해서 반복문이 멈출 때가 바로 시간의 최소값이다. 

#include <iostream>
#include <queue>
#include <utility>
#include <vector>
#include <algorithm>

using namespace std;

int S;
int visit[1001][1001];
int ans;

void BFS(){
    //임티개수,              초, 클립보드 안의 수
    queue<pair<int, pair<int,int>>> que;
    que.push(make_pair(1, make_pair(0,0)));
    visit[1][0] = 1;

    while(!que.empty()){
          
        int s = que.front().first;
        int sec = que.front().second.first;
        int clip = que.front().second.second;
        que.pop();
        
       // cout << s<<"개 / " << sec<<"초  /  " << clip<<"클립보드\n";
       
        if(s==S) {
            ans = sec;
            return;
        }
        
        if(s>0 && s<=1000){
            //복사
            if(visit[s][s]==0){
                visit[s][s] = 1;
                que.push(make_pair(s, make_pair(sec+1, s)));
            }
            
            //하나 삭제
            if(visit[s-1][clip] == 0){
                visit[s-1][clip] = 1;
                que.push(make_pair(s-1, make_pair(sec+1, clip)));
            }
        }
        
        //붙여넣기
        if(clip>0 && s+clip<=1000){
            if(visit[s+clip][clip]==0){
                visit[s+clip][clip] = 1;
                que.push(make_pair(s+clip, make_pair(sec+1, clip)));
            }
        }
    }
}


int main(){

    cin >> S;

    for(int i = 0; i<=1000; i++){
        for(int j = 0; j<=1000; j++){
            visit[i][j] = 0;
        }
    }
    
    BFS();
    cout << ans;

    return 0;
}

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

문제

알고스팟 운영진이 모두 미로에 갇혔다. 미로는 N*M 크기이며, 총 1*1크기의 방으로 이루어져 있다. 미로는 빈 방 또는 벽으로 이루어져 있고, 빈 방은 자유롭게 다닐 수 있지만, 벽은 부수지 않으면 이동할 수 없다.

알고스팟 운영진은 여러명이지만, 항상 모두 같은 방에 있어야 한다. 즉, 여러 명이 다른 방에 있을 수는 없다. 어떤 방에서 이동할 수 있는 방은 상하좌우로 인접한 빈 방이다. 즉, 현재 운영진이 (x, y)에 있을 때, 이동할 수 있는 방은 (x+1, y), (x, y+1), (x-1, y), (x, y-1) 이다. 단, 미로의 밖으로 이동 할 수는 없다.

벽은 평소에는 이동할 수 없지만, 알고스팟의 무기 AOJ를 이용해 벽을 부수어 버릴 수 있다. 벽을 부수면, 빈 방과 동일한 방으로 변한다.

만약 이 문제가 알고스팟에 있다면, 운영진들은 궁극의 무기 sudo를 이용해 벽을 한 번에 다 없애버릴 수 있지만, 안타깝게도 이 문제는 Baekjoon Online Judge에 수록되어 있기 때문에, sudo를 사용할 수 없다.

현재 (1, 1)에 있는 알고스팟 운영진이 (N, M)으로 이동하려면 벽을 최소 몇 개 부수어야 하는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 미로의 크기를 나타내는 가로 크기 M, 세로 크기 N (1 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 미로의 상태를 나타내는 숫자 0과 1이 주어진다. 0은 빈 방을 의미하고, 1은 벽을 의미한다.

(1, 1)과 (N, M)은 항상 뚫려있다.

출력

첫째 줄에 알고스팟 운영진이 (N, M)으로 이동하기 위해 벽을 최소 몇 개 부수어야 하는지 출력한다.

접근 방법

visit[][]로 방문 여부를 체크해야하나 싶었는데, 그렇게 하면 나중에 방문한 경우가 더 적게 벽을 부신 경우가 될 수 있기 때문에 다른 방법을 고려해야 했다.

즉, 다음 방문할 칸이 벽이던 방이던, 갱신 조건(더 적게 벽을 부신 경우)을 만족할 경우에만 Queue에 push 해주면 된다. 그러면 마지막에 cntWall[N][M]에서 상하좌우로 탐색을 할 때 범위체크에서 우/하 방향이 걸러지고 상/좌의 경우에는 갱신조건을 만족하지 못하므로(cntWall가 같으므로) 더이상 Queue 에 Push 하지 않고 while문을 벗어나게 된다. 

(while문 안에 if 조건문으로 탈출 조건을 따로 안 써줘도 된다.)

주의할 점

처음에 메모리 초과가 난 이유가 Queue에 너무 많은 원소가 들어가서였다. 그 코드에서는 범위 체크만 통과하면 바로 Queue에 next 칸을 push 했었다. 

수정된 아래의 코드처럼 갱신 조건을 만족할 때만 Queue 에 push 해주면 메모리초과가 안 뜬다.

#include <iostream>
#include <utility>
#include <queue>

using namespace std;

#define MAX 101

int N,M;
int map[MAX][MAX];
queue<pair<int,int>> que;

int cntWall[MAX][MAX];

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

void BFS(){
    
    while(!que.empty()){

        int r = que.front().first;
        int c = que.front().second;
        que.pop();
        
        for(int i = 0; i<4; i++){
            int nr = r + dr[i];
            int nc = c + dc[i];
            
            if(nr<1 || nr>N || nc<1 || nc>M) continue;		//범위 체크
	
            if(map[nr][nc] == 1){		//다음 칸이 벽일 때
                
                if(cntWall[nr][nc] > cntWall[r][c]+1){		//갱신 조건
                    cntWall[nr][nc] =cntWall[r][c]+1;
                     que.push(make_pair(nr,nc));
                }
                
            }
            else{						//다음 칸이 방일 때
                if(cntWall[nr][nc]>cntWall[r][c]){			//갱신 조건
                    cntWall[nr][nc] = cntWall[r][c];
                    que.push(make_pair(nr,nc));
                }
            }
        }
    }
}

int main(){

    cin >> M >> N;
    string str;
    for(int i = 1; i<=N; i++){
        for(int j = 1; j<=M; j++){
            cntWall[i][j] = 1000;			//최대 값으로 초기 설정
        }
    }
    
    for(int i = 1; i<=N; i++){
        cin >> str;
        for(int j = 1; j<=str.length(); j++){
            map[i][j] = str[j-1]-'0';
        }
    }
    //입력받을 때 동일한 방법
    /* for(int i = 1; i<=N; i++){
        for(int j = 1; j<=M; j++){
            scanf( "%1d", &map[i][j] );
        }
    }*/
   
    
    que.push(make_pair(1,1));
    cntWall[1][1] = 0;          //항상 뚫려 있다고 했으므로 0으로 초기 설정 가능
    
    BFS();
    
    cout << cntWall[N][M];
   
    
    return 0;
}