JArchive 프로그래밍 일기

문제

카드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;
} 

문제

듣보잡 백준 1764번

리뷰

문제 이름이 특이해서 도전해봤다. ㅋㅋ

두개의 string 명단을 비교해서 중복되는 string들을 출력하는 프로그램을 만들어야 한다.

N개를 저장한 벡터를 만든 후, 입력받은 string을 찾으려고 했는데 시간초과 났다.

혼자 헤매다가 결국 질문 게시판을 찾아보니 정렬을 하세요 라는 글이 있었다.

정렬을 하면 같은 이름끼리 붙어있을테니까!! 덕분에 풀 수 있었다.

맞은 코드

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

int N, M, cnt; // 듣. 보
int max_len, min_len;
vector<string> v, answer;
string st;

int main(void){

    cin >> N >> M;

    for(int i = 0; i < N+M; i++){ // N+M개 모두 입력받기 
        cin >> st;
        v.push_back(st);
    }

    sort(v.begin(), v.end()); // 정렬 

     for(int i = 0; i < N+M-1; i++){
        if(v[i] == v[i+1]){   // 정렬하면 같은 단어는 붙어있다.  
            answer.push_back(v[i]);
            cnt++;
        }
    }

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

문제

숨바꼭질6 백준 17087번

리뷰

수빈이의 위치와 1명 이상의 동생들의 위치가 주어진다.

수빈이가 어떤 간격 D로 움직여야 동생들을 전부 만날 수 있냐는 문제다.

수빈이의 위치와 동생들의 위치를 빼서 '거리'를 구한 배열을 만든다.

배열을 전부 순회하면서 '최대공약수'를 구한다.

int gcd(int a, int b){ //  유클리드 호제법으로 구하는 a, b의 최대공약수 
    if(b == 0) return a;
    else return gcd(b, a%b);
}  

동생이 1명이 올수도 있고, 2명일 수도 있으니까 동생 숫자를 유의해야 한다.

맞은 코드

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

int N, S, D; // 동생 수, 수빈 위치  
int A[100001]; // 동생들 위치  

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

    if(b == 0) return a;
    else return gcd(b, a%b);
}  

int main(void){

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

    for(int i = 0; i < N; i++){
        scanf("%d", &A[i]); // 동생의 위치 입력받음  
        A[i] = abs(A[i] - S); // 수빈의 위치와 동생의 위치의 '차이'로 갱신   
    }

    if(N == 1){ // 동생 수 N 1명  

        D = A[0];
    }else if(N == 2){ //동생 2명  

        D = gcd(A[0], A[1]); 
    }else{ 

        D = gcd(A[0], A[1]);

        for(int i = 2; i < N; i++){
            D = gcd(D, A[i]);
        }    
    }

    printf("%d", D);

    return 0;
}

문제

링크와 스타트 백준 15661번

리뷰

14889번 스타트와 링크 문제와 비슷했다.

스타트와 링크는 두 팀이 반드시 N/2 명씩 나뉘어야 했다.

이 문제는 두 팀이 1명 이상이면 된다는 조건이다. 하지만 팀 인원수가 1명이면, 능력치 계산을 못한다.

그래서 S팀이 2명일 때, S팀이 3명일 때, .... S팀이 N-2 명일 때의 경우를 모두 검사했다. DFS로 탐색했다.

    for(int i = 2; i < N-1; i++){  // 2명 부터 n-2명 까지의 범위 전부 검사 
        divideTeam(0, 0, i); 
    }

스타트와 링크 문제 풀이 포스팅

맞은 코드

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

int N;
int answer = 2e9;
bool check[21];
int S[21][21]; 

void countPower(){ // 팀별 능력치 비교  

    vector<int> Steam, Lteam; 
    int Spower=0, Lpower=0; 

    for(int i = 0; i < N; i++){  // 1. vector에 팀별 멤버번호 나눠담기 
        if(!check[i]) {
            Steam.push_back(i);
        }
        else Lteam.push_back(i);
    }    

    for(int i = 0; i < Steam.size(); i++){ // 2. 팀별 능력치 계산  
         for(int j = i+1; j < Steam.size(); j++){
             Spower = Spower + ( S[ Steam[i] ][ Steam[j] ] ) + ( S[ Steam[j] ][ Steam[i] ] );
        }
    }

    for(int i = 0; i < Lteam.size(); i++){  // Steam과 Lteam은 인원수가 다를 수 있다 
         for(int j = i+1; j < Lteam.size(); j++){
            Lpower = Lpower + ( S[ Lteam[i] ][ Lteam[j] ] ) + ( S[ Lteam[j] ][ Lteam[i] ] );
        }
    }

    // 3. 최소값 갱신 
    answer = min(abs(Spower-Lpower),  answer);

    return;
}

void divideTeam(int idx, int cnt, int target){ // N명중에 target 명 고르기  

    if(cnt == target) { // 팀 선택 완료 
        countPower();
        return;
    }

    for(int i = idx; i < N; i++){ // DFS로 완전탐색 

        if(check[i]) continue;

        check[i] = true;
        divideTeam(i+1, cnt+1, target);
        check[i] = false;
    }

}


int main(void){

     cin >> N;

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

    for(int i = 2; i < N-1; i++){ // 2명 부터 n-2명 까지의 범위 전부 검사 
        divideTeam(0, 0, i); 
    }

    cout << answer;

    return 0;
}