JArchive 프로그래밍 일기

문제

분해합 백준 2231번

리뷰

N의 생성자를 찾으려면 1부터 N-1 까지 전부 탐색하면 된다.

N은 1이상 100만 이하의 수가 들어오니까 for문으로 찾아도 2초 시간제한을 초과하지 않는다.

각 자리의 수가 가질 수 있는 최대 숫자는 9이다.

N이 219 일 때, 219는 3 자리수이다.

219에서 9를 3번 빼면 219의 생성자의 최소값을 구할 수 있다. 219 - 9 -9 -9 = 192

따라서 192 부터 218까지 탐색해서 생성자를 구해도 된다. 1부터 탐색할 필요가 없다.

맞은 코드 1

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

int N, answer;

int Sum_total(int n){ 

    int sum = n; // 일단 자기 자신을 더한다. 
    while(n > 0){ 
        sum += (n%10);  // 각 자리수를 더한다 
        n /= 10;
    }
    return sum;
}

int main(void){

    cin >> N;

    for(int i = 1; i < N; i++){

        int sum = Sum_total(i);

        if(sum == N) {
            answer = i;  // 생성자 찾음 
            break;
        }
    }    

    printf("%d", answer);  

    return 0;
} 

맞은 코드 2

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

int N, answer; // 생성자 못찾으면 answer = 0

int main(void){

    cin >> N;

    int tempN = N;
    int len = 0;

    while(tempN > 0){ // 1. N의 자리수 len에 구하기  
        tempN /= 10;
        len++;
    }

    int start_n = len*9; // 자리수 만큼 9를 뺸다 

    for(int i = start_n; i < N; i++){

        int sum = i;
        int temp = i;

        while(temp > 0){ // 2. 각 수의 자리수의 합  
            sum += (temp%10);
            temp /= 10;
        }

        if(sum == N) {
            answer = i; // 생성자 찾음 
            break;
        }
    }    

    printf("%d", answer);

    return 0;
} 

문제

소트인사이드 백준 1427번

리뷰

입력받은 수 N을 한 자리 숫자 씩 잘라서 벡터에 넣는다.

greater() 로 내림차순 정렬한다.

#include <algorithm> 
#include <functional>

sort(v.begin(), v.end(), greater<int>()); // 내림차순 정렬 

맞은 코드

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

int N, len;
vector<int> v;   

int main(void){

    scanf("%d", &N);

    while(N > 0){
        v.push_back(N % 10); // 한 개씩 벡터에 넣는다     
        N /= 10;
        len++;
    }

     sort(v.begin(), v.end(), greater<int>()); // 내림차순 정렬 

     for(int i = 0; i < len; i++){   
        printf("%d",v[i]);
    }

    return 0;
} 

문제

수 정렬하기3 백준 10989번

리뷰

계수정렬(Counting sort) 를 써야 풀리는 문제다.

각 숫자의 개수를 배열 c에 저장한다. 입력받는 숫자는 10,000보다 작거나 같은 자연수이다.

배열 c는 10001 로 크기를 잡는다.

int N, num;
int c[10001];  // 개수를 저장할 배열 

    for(int i = 1; i <= N; i++){ // 1. 각 숫자의 개수를 센다  
        scanf("%d", &num);
        c[num]++;
    }

개수를 센 만큼 숫자 i를 출력 한다.

0개면 출력할 필요 없으니까, 1개 이상인 경우만 출력한다.

for(int i = 1; i < 10001; i++){     // 2. 개수만큼 i를 출력 

    if(c[i]){ // 개수 1이상이면 출력 

        for(int j = 0; j < c[i]; j++){
            printf("%d ", i);
        }
    }
}  

맞은 코드

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

int N, num;
int c[10001];  // 개수를 센다  

int main(void){

    scanf("%d", &N);

    for(int i = 1; i <= N; i++){ // 1. 각 숫자의 개수를 센다  
        scanf("%d", &num);
        c[num]++;
    }

    for(int i = 1; i < 10001; i++){     // 2. 개수만큼 i를 출력 

        if(c[i]){ // 개수 1이상이면 출력 

            for(int j = 0; j < c[i]; j++){
                printf("%d ", i);
            }
        }
    } 

    return 0;
} 

문제

팰린드롬수 백준 1259번

리뷰

수의 숫자들을 뒤에서부터 읽어도 같다면 그 수는 팰린드롬수다.

121, 12421 등은 팰린드롬수다. 123, 1231은 뒤에서부터 읽으면 다르므로 팰린드롬수가 아니다.

% 연산으로 숫자를 벡터에 숫자 한 개씩 넣는다.

가운데 인덱스를 기준으로 양끝 숫자를 비교한다.

맞은 코드

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

int n;

int main(void){

    while(1){
        vector<int> v;
        string st = "yes";
        int len = 0;

        cin >> n;
        if(n==0) break; // 프로그램 종료 

        while(n > 0){
            v.push_back(n % 10); // 한 개씩 벡터에 넣는다     
            n /= 10;
            len++;
        }

        len--;

        for(int i = 0; i <= len/2; i++){ // 가운데 인덱스를 기준으로 양끝 숫자를 비교
            if(v[i] != v[len-i]) st = "no";
        }
        cout << st << '\n';

    }

    return 0;
} 

문제

체스판 다시 칠하기 백준 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;
}