[Algorithm] 1주차 스터디 - 브루트포스, 백트래킹(백준 2309,1065,7568)

문제(2309: 일곱 난쟁이)

www.acmicpc.net/problem/2309

2309번: 일곱 난쟁이

총 9명의 난쟁이의 키가 주어진다. 이 난쟁이들 중 키의 합이 정확히 100이 나오는 경우에 포함되는 자들이 '진짜' 난쟁이들이다.

그렇게 해서 총 7명의 난쟁이를 찾는 것이 문제이다. 찾은 7명의 난쟁이들의 키를 오름차순으로 정렬해서 출력한다.

풀이

처음에는 9명 중 진짜 난쟁이 7명을 찾는 풀이를 생각했었다. 하지만 그것보다는, 차라리 현재 가짜 난쟁이들도 포함된 9명들의 키의 합에서 2명을 선택하여 그 값들을 뺀 값이 100이 되면 나머지 난쟁이들이 진짜 난쟁이들이 된다! 지금생각하니 정말 쉬운 풀이이지만, 부끄럽게도 이걸 쉽게는 생각하지 못했다. 그 다음으로 구현은 쉽다. 

Brute-force 방식으로 2명을 찾는다. 이중 for문을 사용하여 가짜 난쟁이 2명을 색출한다. 가짜 난쟁이를 찾으면(뺀 키의 합이 100이면) 해당 값이 들어있는 배열을 -1로 바꾸고 즉시 return한다.

#include <iostream>
#include <algorithm>
using namespace std;
 
int height[9];
 
int getSum(){
    int sum=0;
    
    for(int i=0;i<9;i++)
        sum+=height[i];
    
    return sum;
}
 
void solution(){
    int sum=getSum();
    
    for(int i=0;i<=7;i++){
        for(int j=i+1;j<=8;j++){
            if(sum-(height[i]+height[j])==100){
                height[i]=-1;
                height[j]=-1;
                return;
            }
        }
    }
}
 
int main(){
    for(int i=0;i<9;i++)
        cin>>height[i];
    
    sort(height,height+9);
    
    solution();
    
    for(int i=0;i<9;i++){
        if(height[i]!=-1)
            cout<<height[i]<<endl;
    }
}

문제(1065: 한수)

www.acmicpc.net/problem/1065

1065번: 한수

숫자 abcd가 주어져 있을 때, b-a=c-b=d-c인 수를 한수라고 한다. 즉, 1234의 경우 2-1=3-2=4-3=1 이므로 1234는 한수이지만 2456의 경우 4-2=2, 5-4=1 이기 때문에 한수가 아니다. N이 주어졌을 때, N보다 크거나 같은 한수의 개수를 출력한다.

 

풀이

각 자리수를 인덱스로 생각해서 풀이 위해 int형 자료를 to_string을 사용하여 string으로 치환하였다. for문을 돌면서 해당 자리수에서 자신의 앞자리, 뒷자리를 각각 뺐을 때의 값이 다르면 한수가 아니다. 한수임을 나타내는 flag를 false로 변경하고 for문을 빠져나온다. for문을 다 돌고 flag가 여전히 true이면 한수이므로 cnt를 1 증가시킨다. 

 

#include <iostream>
#include <algorithm>
#include <string>
using namespace std;
 
int cnt=0;
 
void solution(int n){
    bool flag=true;
    string str=to_string(n);
    
    for(int i=1;i<str.length()-1;i++){
        if(str[i]-str[i-1]!=str[i+1]-str[i]){
            flag=false;
            break;
        }
    }
    
    if(flag)
        cnt++;
}
 
int main(){
    int n;
    cin>>n;
    
    for(int i=1;i<=n;i++){
        solution(i);
    }
    
    cout<<cnt;
}
 

문제(7568: 덩치)

www.acmicpc.net/problem/7568

7568번: 덩치

몸무게와 키가 주어질 때 두 값이 모두 상대방보다 커야 '덩치가 크다.' 라고 말할 수 있다. 덩치 등수를 정하는 규칙은, 자신보다 더 '큰 덩치'의 사람의 수로 정한다. 따라서 자신보다 더 큰 덩치의 사람이 k명이면 그 사람의 덩치 등수는 k+1이 된다.

 

풀이

pair를 사용하여 벡터에 키와 몸무게를 쌍으로 집어넣는다. for문을 돌면서 덩치 등수를 구하는 함수 solution을 호출한다. 

solution함수에서는 자기 자신을 제외한 나머지 모든 사람과 자신을 비교하면서 덩치 등수를 계산한다. 상대방의 키와 몸무게가 모두 자신보다 크면 cnt를 1 증가시킨다. 모든 사람과의 비교가 완료되면 answer에 집어넣는다.

 

#include <iostream>
#include <vector>
using namespace std;
 
vector<pair<int,int>> v;
vector<int> answer;
 
void solution(int idx){
    int cnt=0;
    
    for(int i=0;i<v.size();i++){
        if(i==idx)
            continue;
        if(v[idx].first<v[i].first&&v[idx].second<v[i].second)
            cnt++;
    }
    answer.push_back(cnt);
}
 
int main(){
    int n;
    cin>>n;
    
    for(int i=0;i<n;i++){
        int x,y;
        cin>>x>>y;
        
        v.push_back(make_pair(x,y));
    }
    
    for(int i=0;i<n;i++)
        solution(i);
    
    for(int i=0;i<n;i++)
        cout<<answer[i]+1<<' ';
}