JArchive 프로그래밍 일기

문제

체스판 다시 칠하기 백준 1018번

리뷰

주어진 체스판을 WBWB 패턴의 8 x 8 크기의 체스판, 또는 BWBW 패턴으로 바꾸려고 한다.

이미 목표한 2종류 패턴의 체스판을 string 배열로 만들어 둔다.

string B[51];   // 보드  ( 가로 세로는 최대 50보다 작거나 같다.)

string W_pattern[8] = {
    {"WBWBWBWB"},
    {"BWBWBWBW"},
    {"WBWBWBWB"},
    {"BWBWBWBW"},
    {"WBWBWBWB"},
    {"BWBWBWBW"},
    {"WBWBWBWB"},
    {"BWBWBWBW"}
}; 

string B_pattern[8] = {
    {"BWBWBWBW"},
    {"WBWBWBWB"},
    {"BWBWBWBW"},
    {"WBWBWBWB"},
    {"BWBWBWBW"},
    {"WBWBWBWB"},
    {"BWBWBWBW"},
    {"WBWBWBWB"}
}; 

주어진 보드의 시작점을 달리하면서

시작점에서 W_pattern이랑 다른 칸의 개수를 세고, B_pattern이랑 다른 칸의 개수를 센다.

    for(int i = 0; i+7 < N; i++){
        for(int j = 0; j+7 < M; j++){
            min_cnt = min(min_cnt, Bcheck(i, j) );
            min_cnt = min(min_cnt, Wcheck(i, j) );
        }
    } 

맞은 코드

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

int N, M;         // 세로, 가로  
string B[51];   // 보드  
int min_cnt = 2e9;

string W_pattern[8] = {
    {"WBWBWBWB"},
    {"BWBWBWBW"},
    {"WBWBWBWB"},
    {"BWBWBWBW"},
    {"WBWBWBWB"},
    {"BWBWBWBW"},
    {"WBWBWBWB"},
    {"BWBWBWBW"}
}; 

string B_pattern[8] = {
    {"BWBWBWBW"},
    {"WBWBWBWB"},
    {"BWBWBWBW"},
    {"WBWBWBWB"},
    {"BWBWBWBW"},
    {"WBWBWBWB"},
    {"BWBWBWBW"},
    {"WBWBWBWB"}
}; 

int Wcheck(int x, int y){

    int n_limit = x+8;
    int m_limit = y+8;
    int cnt = 0;

    for(int i = x; i < n_limit; i++){
        for(int j = y; j < m_limit; j++){
            if(B[i][j] != W_pattern[i-x][j-y] ) cnt++;
        }
    }
    return cnt; 
}


int Bcheck(int x, int y){

    int n_limit = x+8;
    int m_limit = y+8;
    int cnt = 0;

    for(int i = x; i < n_limit; i++){
        for(int j = y; j < m_limit; j++){
            if(B[i][j] != B_pattern[i-x][j-y] ) cnt++;
        }
    }
    return cnt; 
}


int main(void){

     scanf("%d %d", &N, &M);

     for(int i = 0; i < N; i++){
         cin >> B[i];
    }

    for(int i = 0; i+7 < N; i++){
        for(int j = 0; j+7 < M; j++){
            min_cnt = min(min_cnt, Bcheck(i, j) );
            min_cnt = min(min_cnt, Wcheck(i, j) );
        }
    } 

    printf("%d", min_cnt);

    return 0;
} 

문제

골드바흐 파티션 백준 17103번

리뷰

골드바흐의 추측과 비슷한 문제다.

주의할 점 ! 같은 수 조합이라면 순서가 다르더라도 같은 파티션으로 생각한다는 것이다.

1. 에라토스테네스의 체를 이용하여 소수를 구한다. --> Prime 함수.
2. TC 개수와 정수 N을 입력받는다. 정수 N은 짝수이고, 2 < N ≤ 1,000,00
3. 가장 작은 소수부터 반복을 진행한다.

for(int i = 2; i < N; i++){ // 소수가 현재 입력 수보다 작은 동안.

    if((p[N-i] + p[i]) == N){

        cnt++;

        if(N-i == i){ // 10 = 5+5; 의 경우를 고려. 
            cnt++; 
        }
    }
}

소수끼리의 합으로 N을 표현할 수 있는지 확인한다.

5+5 처럼 같은 소수를 반복사용할 수 있으니까 N-i == i 인 경우에도 cnt 를 증가시킨다.

맞은 코드

#include <iostream>
#include <algorithm> 
#define MAX 1000000
using namespace std;


int TC;
int p[MAX+1];

void Prime(){

    p[0] = p[1] = 0; // 0과 1은 소수가 아니다.  

    for(int i = 2; i <= MAX; i++){ // 자기 자신을 저장 
        p[i] = i;
    } 

    for(int i = 2; i*i <= MAX; i++){ // 소수의 배수들를 0으로 지운다.  

        if(p[i] == i){

            for(int j = i*i; j <= MAX; j += i ){ // i만큼 건너 뛰어서 배수 찾기.
                p[j] = 0; 
            }
        } 
    }
}

int main(void){

    Prime(); // 에라토스테네스의 체 

    cin >> TC;

    while(TC--){

        int N = 0;
        cin >> N;
        int cnt = 0;

        for(int i = 2; i < N; i++){ // 소수가 현재 입력 수보다 작은 동안.

            if((p[N-i] + p[i]) == N){

                cnt++;

                if(N-i == i){ // 10 = 5+5; 의 경우를 고려. 
                    cnt++; 
                }
            }
        }

        printf("%d\n", cnt/2);

    }

    return 0;
} 

문제

요세푸스 문제 0 백준 11866번

리뷰

K번째 수를 세는 문제다. 큐를 이용해 풀 수 있다.

일단 꺼낸다 pop한다. 몇 번째인지 cnt를 확인한다. K번째면 답에 넣고, 아니면 다시 push 한다.

맞은 코드

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

int N, K, n;
queue<int> q;
vector<int> v;

int main(void){

    scanf("%d %d", &N, &K);
      for(int i=1; i<=N; i++){
        q.push(i);          
    }

     int cnt = 0;

     while(!q.empty()){

         int num = q.front(); 
         q.pop(); // 일단 꺼낸다.
         cnt++;

         if(cnt == K){ // K번째 일 때 벡터에 넣는다 
              v.push_back(num);
             cnt = 0;
        }else{
            q.push(num); // 다시 넣는다. 
        }
    }

    // 출력
    cout << '<';
    for(int i = 0; i < v.size()-1; i++ ){
        printf("%d, ", v[i]);
    }
    printf("%d>", v[v.size()-1]);

    return 0;
} 

문제

카드2 백준 2164번

리뷰

벡터로 하면 시간 초과가 난다.

삽입, 삭제가 자주 일어나니까 큐나 리스트로 풀어야 한다.

pop 하고 나서, 큐의 크기를 바로 체크해야 함을 생각해내지 못해서 오래걸린 문제.

맞은 코드

#include <iostream>
#include <queue>
#include <algorithm> 
using namespace std;

int num, N, M;
queue<int> q;

int main(void){

      cin >> N;

      for(int i = 1; i <= N; i++) {
          q.push(i);
    }

    if(q.size() == 1) cout << 1;
    else {

        int res = 0;

        while(1){
            q.pop();

            if(q.size() == 1) {
                res = q.front(); break;
            }
             int fro = q.front();
             q.pop();          // 맨앞 삭제 
              q.push(fro);     // 맨앞 숫자를 뒤에 푸시.
        }

        cout << res;
    }


    return 0;
} 

문제

ACM 호텔 백준 10250번

리뷰

H층 W호의 방을 가진 호텔이 있다.

H=6, W=12 라면, 총 72개의 방이 있는데, 엘리베이터는 1호 쪽에만 있다.

1 ≤ H, W ≤ 99, 1 ≤ N ≤ H × W 라는 제한이니까 층과 호는 2자리수 까지만 입력이 들어올 수 있다.

따라서, 12호(2자리 수의 W) 까지 존재하는 호텔은 2호에 배정할 때 02호 라고 출력해야 한다.

예를 들어, H=3, W=5 라면, N번째 손님의 배정 순서는 아래와 같다.

N / W 으로 '호' 를 구할 수 있다. N % W == 0 인 경우, 나누어 떨어지니까 1 크게 나온다.

N % W 으로 '층' 을 구할 수 있다.

단, N % W == 0 이라면, 층을 H로 대체해 줘야 한다.

맞은 코드

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

int TC, H, W, N;

int main(void){

    cin >> TC;

    while(TC--){
        cin >> H >> W >> N;

        int level = N % H;   // 층  
        int ho = N / H + 1;   // 호

        if(level == 0){
            level = H;
        } 

        if(N % H == 0){
            ho--;
        }

        cout << level*100 + ho << '\n';
    }

    return 0;
} 

문제

이항 계수1 백준 11050번

리뷰

N개중에 K개를 고르는 이항계수를 작성하는 문제다.

파스칼의 삼각형도 이항계수를 기반으로 풀 수 있다.

"재귀로 푼 이항계수"포스팅의 도움을 받았다. 

맞은 코드

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

int N, K;

int bi(int n, int k){

    if(n == k || k == 0) return 1;
    else return bi(n-1, k) + bi(n-1, k-1);

}

int main(void){

    cin >> N >> K;
    cout << bi(N, K);

    return 0;
} 

문제

단어 정렬 백준 1181번

리뷰

단순히 sort 하면 되는 줄 알고 풀었는데, 아니었다.

단어 길이가 짧을 수록 앞에 와야 한다.

단어 길이가 다르다면, 길이가 짧은 것이 앞으로 와야 한다.

길이가 같으면, 사전순으로 정렬 한다.

sort 의 기준이 되는 compare 함수를 작성했다.

bool compare(string a, string b){
    if(a.size() == b.size() ) return a < b;  // 사전순 정렬 
    else return a.size() < b.size(); // 길이 긴 것이 뒤로 
}

sort(v.begin(), v.end(), compare);

맞은 코드

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

vector<string> v;

bool compare(string a, string b){
    if(a.size() == b.size() ) return a < b;
    else return a.size() < b.size();
}

int main(void){

     int cnt = 0;
    cin >> cnt;

    while(cnt--){
        string input;
        cin >> input;

        // 중복 없으면 푸시  
        if(find(v.begin(), v.end(), input) == v.end())    v.push_back(input);     
    } 

    sort(v.begin(), v.end(), compare);

    for(int i = 0; i < v.size(); i++){
        cout << v[i] << '\n';
    }

    return 0;
}