JArchive 프로그래밍 일기

문제

퇴사 백준 14501번

리뷰

완전 탐색으로 풀었다.

오늘 상담을 한다/안한다를 구분해서 재귀를 두 번 호출한다.

advice(day + T[day], sum + P[day]); // 오늘 상담한다  

advice(day + 1, sum);  // 오늘 상담 안하고 다음날로 지나간다  

코드

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

// 퇴사  

int N;
int T[16];
int P[16]; 
int max_sum;

void advice(int day, int sum){

    if(N == day){ // 종료 
        max_sum = max(max_sum, sum);
        return;
    }

    if(N < day){ // 제한 날짜 초과  
        return;
    }

    advice(day + T[day], sum + P[day]); // 오늘 상담한다  
    advice(day + 1, sum);  // 오늘 상담 안하고 다음날로 지나간다  
}

int main(void){

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

    cin >> N;

     for(int i = 0; i < N; i++){
         scanf("%d %d", &T[i], &P[i]);
    }  // 입력받기 끝  

    advice(0, 0);

    cout << max_sum;

    return 0;    
}

문제

차이를 최대로 백준 10819번

리뷰

do while 문을 이용해서 next_permutation 함수가 false를 반환하기 전까지 계속 출력시킨다.

abs 함수를 검색해보면서 새로운 걸 배웠다.

#include <cstdlib>
int abs(int a)

#include <cmath>
double abs(double a)

int 형의 절대값 함수는 cstdlib 에 있고,

double, float 형의 절대값 함수는 cmath에 있다.

참고로 C언어 에서 int형 절대값 함수는 stdlib.h 에 속하고 double형 절대값 함수 abs는 math.h 에 있다.

#include <stdlib.h>
int abs(int a)

#include <math.h>
double fabs(double a)

next_permutation() 함수

혼자 푸는데 자꾸 틀려서 다른 분들 코드를 봤는데, 순열함수 전에 sort() 를 한 것이 내 코드와의 차이였다.

#include <algorithm>

bool next_permutation (BidirectionalIterator first, BidirectionalIterator last);

이 함수는 주어진 수열의 다음순열이 없으면 false 를 반환해준다.

'다음' 순열의 기준은 현재 순열보다 내림차순된 순열이 있느냐/없느냐다.

예를 들어, 1234 의 다음 순열은 1243

1234 -> 1243 -> 1324 -> 1342 ... -> 4321 이처럼 첫 수열은 오름차순이고 맨 마지막 수열은 내림차순임을 이용하여 구현된 함수다.

따라서 처음에 next_permutation 에 4321 을 넣고 실행하면, 이미 전부 내림차순이므로( == 다음순열이 없다고 판단) false 반환하고 종료한다.

cplusplus.com 의 next_permutation 예시는 아래와 같다.

// next_permutation example
#include <iostream>     // std::cout
#include <algorithm>    // std::next_permutation, std::sort

int main () {
  int myints[] = {1,2,3};

  std::sort (myints,myints+3);

  std::cout << "The 3! possible permutations with 3 elements:\n";
  do {
    std::cout << myints[0] << ' ' << myints[1] << ' ' << myints[2] << '\n';
  } while ( std::next_permutation(myints,myints+3) );

  std::cout << "After loop: " << myints[0] << ' ' << myints[1] << ' ' << myints[2] << '\n';

  return 0;
}

// output 
The 3! possible permutations with 3 elements:
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1
After loop: 1 2 3

코드

#include <iostream>
#include <cstdlib> // abs()
#include <algorithm> //  next_permutation( )
using namespace std;

// 차이를 최대로  

int N;
int a[10];

int main(void){

    int max_value = 0;

    cin >> N;

     for(int i = 0; i < N; i++){
         scanf("%d", &a[i]);
    }  // 입력받기 끝  

    sort(a, a+N); // 정렬 

     do{
         int max_tmp = 0;

         for(int i = 0; i < N-1; i++){
             max_tmp += abs(a[i]-a[i+1]);
        } 

        max_value = max(max_tmp, max_value);

    }while(next_permutation(a, a+N));

    cout << max_value;

    return 0;    
}

문제

날짜 계산 백준 1476번

리뷰

주어진 E S M이 몇년도 인지 맞추는 문제다. (1 ≤ E ≤ 15, 1 ≤ S ≤ 28, 1 ≤ M ≤ 19)

년도는 최소 1년 부터 15 x 28 x 19 년까지 가능하니까 완전 탐색으로 풀 수 있다.

E, S, M 모두 15, 28, 19 를 주기로 반복되니까

year에서 E를 뺀 수가 15로 나누어 떨어지는지 확인하면 된다.

S, M 을 빼서 똑같이 확인한다.

코드

#include <iostream>
#include <algorithm>
#define E_MAX 15
#define S_MAX 28
#define M_MAX 19
using namespace std;

int E, S, M;

int main(void){

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

    cin >> E >> S >> M;

    int year = 1;

    while(1){ // 15, 28, 19의 배수가 되면 종료  

        if( (year-E) % E_MAX == 0 &&  (year-S) % S_MAX == 0  &&  (year-M) % M_MAX == 0 ){
            cout << year;
            break;
        }

        year++;
    }

    return 0;

}

문제

카잉달력 백준 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;
}