JArchive 프로그래밍 일기

문제

카잉달력 백준 6064번

리뷰

ㅠㅠ 풀고 해설보며 이해하는 데 오래걸린 문제다.

x는 M 주기로 돌아가고, y는 N 주기로 돌아간다.

그러니까 답 i = i % M == x 가 된다. 또한 i % N == y 를 만족해야 한다.

그래서 i를 찾는 for문을 M 크기로 증가시키는 것이다.

i는 x로 시작한다.

종말 날짜 endday는 M과 N의 최소공배수다. 이것은 gcd 함수로 계산할 수 있다.

아래 코드를 보자.

while(T--){ // 테스트 케이스 만큼 반복 

        cin >> M >> N >> x >> y;

        int i = x; // x로 시작 
         int endday = lcm(M, N);
        int result = -1; // 실패할 경우 답의 base case

        for(i = x; i <= endday; i += M){ // x는 M만큼 건너뛴다 

            ...
        }

        cout << result << '\n';
    }

이제 for문 안에서는 y를 찾아야 한다.

y는 N과 똑같을 수도 있고, 아닐 수도 있다.

가장 쉬운 케이스는 i가 N으로 나눈 나머지가 y 인 경우다. 바로 정답이 되고 i 를 출력하면 된다.

y == N 인 경우, 그 순간의 i 가 N으로 나누어 떨어지는 숫자인지 확인해야 한다.

for(i = x; i <= endday; i += M){ // x는 M만큼 건너뛴다 

    // i를 N 으로 나눈 나머지가 y 이라면 만족 
    // y == N 인 경우에는, i 가 N으로 나누어 떨어져야 만족 
    if( (y == N && i % N == 0 ) || (i % N == y) ){ 
        result = i; 
        break;
    }
}

코드

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

// 카잉달력

int T, M, N, x, y;

int gcd(int a, int b){ // 최대공약수

    while(b != 0){
        int t = a % b;
        a = b;
        b = t;
    } 

    return a;
} 

int lcm(int a, int b){ // 최소공배수 
    return (a * b) / gcd(a,b);
}

int main(void){

    cin >> T;

    while(T--){

        cin >> M >> N >> x >> y;

        int i = x; // x로 시작 
         int endday = lcm(M, N);
        int result = -1; // 실패할 경우 답의 base case

        for(i = x; i <= endday; i += M){ // x는 M만큼 건너뛴다 

            // i를 N 으로 나눈 나머지가 y 이라면 만족 
            // y == N 인 경우에는, i 가 N으로 나누어 떨어져야 만족 
            if( (y == N && i % N == 0 ) || (i % N == y) ){ 
                result = i; 
                break;
            }

        }

        cout << result << '\n';
    }

    return 0;    
}

반례

백준 질문게시판 - jh05013님의 반례 및 FAQ

그 외 참고 해설

15
40000 39999 39999 39998
40000 39999 40000 39999
40000 40000 40000 39999
40000 39998 40000 39997
39999 2 39998 2
3 40000 3 39999
40000 3 40000 3
8 2 4 2
10 12 2 12
12 10 12 10
12 10 1 1
12 6 12 6
10 1 5 1
1 10 1 5
1 1 1 1

// 답 
1599959999
1599960000
-1
-1
39998
39999
120000
4
12
60
1
12
5
5
1

문제

테트로미노 백준 14500번

리뷰

완전 탐색으로 풀었다.

5종류의 테트로미노가 주어진다. 얘네를 대칭, 회전시킬 수 있다.

한 칸마다 숫자가 쓰여진 크기가 NxM인 종이가 있다.

이 종이에 테트로미노 '하나'를 놓을 때, 테트로미노가 놓인 칸에 쓰여있는 수들의 최댓값을 구하면 된다.

도형을 놓는 경우의 수

1x4 모양 도형은 세로/가로 이렇게 2가지 경우가 있다. 2x2 모양 도형은 1가지 경우 뿐이다.

나머지 3가지 도형은 회전/대칭 시켜보면 16가지가 나온다.

그래서 도형을 놓는 모양의 경우의 수는 총 19가지다.

1x4 , 4x1, 2x2 를 제외하고서는 나머지 도형들이 인덱스 처리하기가 까다로워서 자꾸 틀렸다.

그래서 2x3 크기의 6칸의 합을 더해놓고, 6칸 중에 2칸의 숫자를 빼는 것으로 코드를 바꿨다.

예를 들어, 아래처럼 세로 2 가로 3, 의 네모칸이 있으면 숫자 총합을 구해둔다.

[ O ] [ O ] [ O ]

[ O ] [ O ] [ O ]

6칸 총합에서 윗줄에서 첫번째, 세번째 숫자 자리의 값를 빼면 ' ㅗ ' 모양 도형의 합을 구한것과 같다.

[ X ] [ O ] [ X ]

[ O ] [ O ] [ O ]

다른 위치를 빼면 'ㄴ' 모양 도형이 합을 구한것과 같게 된다.

[ O ] [ X ] [ X ]

[ O ] [ O ] [ O ]

다 풀고 나니깐 DFS로 푸신 분 코드가 있었다.

코드

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

// 테트로미노  (BOJ 14500) 

int N, M;
int B[501][501]; 
int ans;
int i, j, a, b;

int main(void){

    cin >> N >> M; // 세로, 가로  

    int sum=0;


    // 입력받기
    for(i=1; i <= N; i++){ // 행 (세로)

        for(j=1; j <= M; j++){ // 열 (가로)
             cin >> B[i][j];
        } 
    }


    for(i=1; i <= N; i++){ // 행 (세로) 

        for(j=1; j <= M; j++){ // 열 (가로) 

            if(j+3 <= M){ //   1x4 
                sum = B[i][j] + B[i][j+1] + B[i][j+2] + B[i][j+3];
                ans = max(ans, sum);
            }

            if(i+3 <= N){ //   4x1
                sum = B[i][j] + B[i+1][j] + B[i+2][j] + B[i+3][j];
                ans = max(ans, sum);
            }

            if(j+1 <= M && i+1 <= N){ // 2x2 네모  
                sum = B[i][j] + B[i+1][j] + B[i][j+1] + B[i+1][j+1];
                ans = max(ans, sum);
            }


            // 세로2 가로3 내부에서 
            if(i+1 <= N && j+2 <= M){

                int six_sum = 0;

                for(a=i; a <= (i+1); a++){
                    for(b=j; b <= (j+2); b++){
                        six_sum += B[a][b];
                    }
                }

                sum = six_sum - (B[i+1][j] + B[i+1][j+2]);
                ans = max(ans, sum);

                sum = six_sum - (B[i][j] + B[i][j+2]);
                ans = max(ans, sum);

                sum = six_sum - (B[i][j] + B[i+1][j+2]);
                ans = max(ans, sum);

                sum = six_sum - (B[i+1][j] + B[i][j+2]);
                ans = max(ans, sum);

                sum = six_sum - (B[i][j+1] + B[i][j+2]);
                ans = max(ans, sum);

                sum = six_sum - (B[i][j] + B[i][j+1]);
                ans = max(ans, sum);

                sum = six_sum - (B[i+1][j] + B[i+1][j+1]);
                ans = max(ans, sum);

                sum = six_sum - (B[i+1][j+1] + B[i+1][j+2]);
                ans = max(ans, sum);
            } 

            // 세로3 가로2 내부에서 
            if(i+2 <= N && j+1 <= M){

                int six_sum = 0;

                for(a=i; a <= (i+2); a++){
                    for(b=j; b <= (j+1); b++){
                        six_sum += B[a][b];
                    }
                }

                sum = six_sum - (B[i][j+1] + B[i+1][j+1]);
                ans = max(ans, sum);

                sum = six_sum - (B[i][j] + B[i+1][j]);
                ans = max(ans, sum);

                sum = six_sum - (B[i+1][j] + B[i+2][j]);
                ans = max(ans, sum);

                sum = six_sum - (B[i+1][j+1] + B[i+2][j+1]);
                ans = max(ans, sum);

                sum = six_sum - (B[i][j+1] + B[i+2][j+1]);
                ans = max(ans, sum);

                sum = six_sum - (B[i][j] + B[i+2][j]);
                ans = max(ans, sum);

                sum = six_sum - (B[i][j] + B[i+2][j+1]);
                ans = max(ans, sum);

                sum = six_sum - (B[i+2][j] + B[i][j+1]);
                ans = max(ans, sum);
            }     
        }
    }

    cout << ans;

    return 0;

}

문제

오큰수 백준 17298번

리뷰

단순하게 이중for문으로 풀었을 때 시간초과났다.

직전 수와 그동안 만났던 값들 중의 최대값을 저장해 볼까 하면서 풀었을 땐 틀렸다.

결국 다른 분들의 해설을 찾아봤다.

스택을 이용한 풀이다.

크기가 N인 A배열에는 주어진 수열을 저장한다.

크기가 N인 v벡터는 -1로 초기화 해둔다. 답으로 반환할 수열을 저장한다.

v벡터에는 A의 '인덱스'를 저장한다.

int N;
int A[MAX_LEN+1];    

stack<int> st;
vector<int> v(N, -1); // 반환할 수열  

for(int i = 0; i < N; i++){
    scanf("%d", &A[i]);
}

A[0] 에서는 while문 조건을 불만족하니까. 0을 스택에 push 한다.

오큰수를 찾지 못한 수의 ''인덱스''가 stack st에 쌓여가는 것이다.

스택st 의 top에 있는 인덱스의 A 값이 현재값(A[i]) 보다 작으면, 현재값이 A[ st.top() ]의 오큰수다.

그래서 top 값을 v벡터에 값을 넣어준다.

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

    while(!st.empty() && A[st.top()] < A[i]){
        v[st.top()] = A[i];
        st.pop();
    }

    st.push(i);
}

A[ st.top() ]의 오큰수를 찾아줬으니 pop() 한다.

혼자 해봤을 때 안풀려서 약올랐던(?)문제다.

코드

#include <iostream>
#include <stack>
#include <vector>
#define MAX_LEN 1000000
using namespace std;

int N;
int A[MAX_LEN+1];

int main(void){

    freopen("input.txt", "rt", stdin);

    cin >> N ;

    stack<int> st;
    vector<int> v(N, -1); // 반환할 수열  

    for(int i = 0; i < N; i++){
        scanf("%d", &A[i]);
    }

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

        while(!st.empty() && A[st.top()] < A[i]){
            v[st.top()] = A[i];
            st.pop();
        }

        st.push(i);
    }

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

    return 0;

}

문제

단어 뒤집기 백준 17413번

리뷰

삽질하면서 배운것이 많은 문제.

1. getline 함수와 cin.getline 함수가 다르다는 것을 배웠다!!

cin.getline( *char , 크기 ) 

cin.getline 함수는 <iostream> 에 속한 cin 의 멤버함수다. 

문자열 입력받는 12가지 방법을 아주 자세히 포스팅해주셨다. C++스러운 코드 문자열 입력받는 12가지 방법

#include <iostream>
using namespace std;


char C[10];
cin.getline(C, 10); // char* 인자와 입력받을 크기를 받는다. 

cin.getline(C, sizeof(C)); 

getline() 함수는 <string>에 속해 있어서 인자도 string을 받는다.

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

string st;
getline(cin, st);

// '\n' 개행문자가 나올 때 까지 입력받는다. 개행문자까지 입력받고 버퍼는 비운다. 

2. 주의할 점

cin과 getline을 같이 쓸 때 주의할 점이 있다.

cin 이후에 버퍼를 비워주는 함수 cin.ignore() 를 실행해서 버퍼를 비워주고 난 후, getline()을 써야 한다.

cin은 띄어쓰기, 엔터, 탭은 출력하지 않지만 버퍼에 남아있다.

3. 그 외 힌트 얻은 질문 게시판 글

문자열 입력받을 때 파일의 끝인 EOF(이스케이프 시퀀스) 로 문자열이 끝난다.

문자열 입력받을 배열은 문제에 제한된 최대 크기보다 10정도 크게 잡는게 좋다.

getline 함수를 cin.getline() 함수로 수정하고, 띄어쓰기 출력 문제 조건문 처리를 수정하고나서야 맞출 수 있었다. 뿌듯했다.

코드

#include <iostream>
#include <string> // string을 인자로 받는 getline()
#include <cstring> //char* 를 인자로 받는 cin.getline()
#include <stack>
using namespace std;

// 단어뒤집기 2  

char S[100002];
stack<char> st;

int main(void){

    bool in_tag = false; // 현재 인덱스가 태그 안에/밖에 있는지 구분 

    cin.getline(S, sizeof(S));

      for(int i = 0; i < sizeof(S); i++){

         if(S[i]=='<'){ //태그 시작  

            in_tag = true; 

            if(!st.empty()){
                while(!st.empty()){
                    cout << st.top();
                    st.pop();
                }
            }    
        }

        if(S[i] == ' ' || S[i] == NULL){  // 공백만나면 스택비우기  

            while(!st.empty()){
                cout << st.top();
                st.pop();
            }

            if(S[i] == ' '){
                cout << ' ';
            }

        }else if(!in_tag){ // 일반- 큐에 넣기   

            char ch = S[i]; 
            st.push(ch);

        }else if(in_tag){ // 태그 내부 - 그대로 출력 

            cout << S[i];    

            if(S[i]=='>'){ // 태그 끝이면, in_tag가 끝났다고 바꿔주고 끝낸다. 
                in_tag = false; 
            }
        }

    }

    return 0;
}

문제

암호 만들기 백준 1759번

리뷰

완전탐색 문제다.

주어진 C개의 문자 중에서 L개만 선택해서 만들 수 있는 암호의 개수를 센다.

암호 문자열의 조건은 자음이 2개 이상, 모음이 1개 이상이면 답이 된다.

1. 암호를 전부 만들어 본다. --> 함수 bf()
2. L개의 문자를 고른 순간, 자음/모음 개수 조건을 충족하면 출력해준다. --> 함수 check()

L개를 다 고를 때 까지 주어진 문자들을 순회하며 (idx 변수 ) string st 에 이어 붙여본다.

string st 의 길이가 L개가 되는 순간, 자음/모음 개수 조건을 확인한다.

idx 위치의 문자를 선택 한다/안한다로 재귀 호출한다.

void bf(string st, int idx){

    if(L == st.length()){ // L 개 다 고름  

        if(check(st)){ // 자음 모음 개수 충족 여부 확인  
            cout << st << '\n';
        }
        return;
    }

    if(alpha.size() <= idx) return; // 끝 

    bf(st + alpha[idx], idx+1); // idx 문자를 선택해서 st에 이어붙인다.  

    bf(st, idx+1);  // 선택안하고 지나간다. 

}

자음/모음 조건을 확인하는 함수다.

vector STL이 제공하는 find()의 기능을 활용했다.

momo 에서 x가 존재하면 x의 인덱스를 반환하고, 없으면 end()를 반환한다.

vector<char> momo{'a', 'e', 'i', 'o', 'u'};

bool check(string &pw){ // 자음 모음 개수 세기 

    int ja = 0, mo = 0;    

    for(char x : pw){

        if( find(momo.begin(), momo.end(), x) != momo.end() ){
            mo++;
        }else{
            ja++;
        }
    }

    return (ja >= 2 && mo >= 1); 
}

코드

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

int L, C;
vector<char> alpha; // 주어진 문자 
vector<char> momo{'a', 'e', 'i', 'o', 'u'};

bool check(string &pw){ // 자음 모음 개수 세기 

    int ja = 0, mo = 0;    

    for(char x : pw){

        if( find(momo.begin(), momo.end(), x) != momo.end() ){
            mo++;
        }else{
            ja++;
        }
    }

    return (ja >= 2 && mo >= 1);
}


void bf(string st, int idx){

    if(L == st.length()){ // L 개 다 고름  

        if(check(st)){ // 자음 모음 개수 충족 여부 확인  
            cout << st << '\n';
        }
        return;
    }

    if(alpha.size() <= idx) return;

    // 선택 
    bf(st + alpha[idx], idx+1);
    // 선택안함 
    bf(st, idx+1); 

}

int main() {

    string st; // 암호  
    char ch;    

    cin >> L >> C; //C개 중에 L개를 골라 암호 만들기  

    for(int i = 0; i < C; i++){    // 주어진 문자 
        cin >> ch;
        alpha.push_back(ch);
    } // 입력받기 끝 

    sort(alpha.begin(), alpha.end()); // 오름차순 정렬 

    bf(st, 0); // 모든 조합 시도 

    return 0;
}

문제

단어 뒤집기 백준 9093번

리뷰

scanf 로 테스트케이스 숫자를 받고나서 자꾸 공백이 찍히는게 이상해서 구글링을 했다.

getline 함수로 문장을 받기 전에, 버퍼를 비워줘야 했다!!

**코드

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

char A[1002];

int main(void){

    freopen("input.txt", "rt", stdin);

     int N = 0;
     cin >> N; 

     string bufferflush; 
     getline(cin, bufferflush); // 버퍼를 비운다 

     while(N--){

         string st, rev_st;
         getline(cin, st); // 한 줄 입력받기 

         for(int i = 0; i < st.length(); i++){

             if(st[i] == ' '){
                 // 띄어쓰기 만날 때 마다 뒤집은 것 출력
                reverse(rev_st.begin(), rev_st.end());
                cout << rev_st << ' ';
                rev_st.clear(); // 출력 끝났으니까 비운다 

            }else{
                rev_st += st[i]; 
            }
        }

        // 문장의 마지막 단어 출력 후 개행  
        reverse(rev_st.begin(), rev_st.end());
        cout << rev_st << endl;
    }

     return 0;
}

문제

문자열 분석 백준 10820번

리뷰

오늘의 교훈은... 문자 초기화를 제대로 하자!!! 였다.

ROT13 문제를 풀고나서 비슷하길래 자신있게 풀었는데,

int lower=0, upper=0, num=0, space=0; // 이렇게 초기화 해야하는데. 

int lower, upper, num, space=0; // 이렇게 해서. 대여섯번을 뭐가 잘못됬나 헤맸다.

지역변수는 초기화를 잘 하자.

코드

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

int main () {

    string s;

    while(getline(cin, s)){ // 공백 포함한 문자열 받을 때는 getline이 좋다.

        int lower=0, upper=0, num=0, space=0; // 초기화를 잘 하자. 

        for(int i = 0; i < s.length(); i++){

            if(islower(s[i]) ) lower++;
            else if(isupper(s[i]) ) upper++;
            else if(isdigit(s[i]) ) num++;
            else if(' ' == s[i]) space++;
        }

        printf("%d %d %d %d\n", lower, upper, num, space);
    }

    return 0;
}