백준 연습 #2

문제는 3문제였고 자기 전에 1시간 정도 연습을 진행했다.

올솔 ㅎ

1. 한 줄로 서기 (Silver 2)

www.acmicpc.net/problem/1138

1138번: 한 줄로 서기

N<=10이므로 누가봐도 백트래킹이다.

저런 문제는 빠르게 머리를 밀어주자.

#include <bits/stdc++.h>
#define MEM 155
#define sanic ios_base::sync_with_stdio(0)
using namespace std;
typedef long long ll;
const ll MOD = 1e9+7;
ll n,m,k;
ll s[MEM];
ll a[MEM];
main() {
    sanic;
    cin >> n;
    for(int i=0; i<n; i++)
        cin >> s[i];
    for(int i=0; i<n; i++)
        a[i] = i+1;
    do{
        bool b=1;
        for(int i=1; i<=n; i++){
            ll cnt=0;
            for(int j=0; j<n; j++){
                if(a[j]==i) break;
                if(a[j]>i) cnt++;
            }
            if(cnt!=s[i-1]) {b=0;break;}
        }
        if(b){
            for(int i=0; i<n; i++)
                cout << a[i] << ' ';
            return 0;
        }
	}while(next_permutation(a,a+n));
}

2. 이모티콘 (Gold 5)

www.acmicpc.net/problem/14226

14226번: 이모티콘

처음엔 dp 느낌을 많이 받았으나 3번을 처리를 못하는 단점이 있다.

그러므로 bfs+dp를 통해 최소 시간을 알아내자.

dp[i][j] = 입력한 이모티콘 길이가 i이고 클립보드에 있는 이모티콘 길이가 j일때 최소 입력 수

#include <bits/stdc++.h>
#define MEM 3055
#define sanic ios_base::sync_with_stdio(0)
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pi;
const ll MOD = 1e9+7;
ll n,m,k;
ll dp[MEM][MEM];
queue<pi> q;
main() {
    sanic;
    cin >> n;
    q.push({1,0});
    while(!q.empty()){
        ll a=q.front().first,b=q.front().second;
        q.pop();
        //cout << a << ' ' << b << '\n';
        if(a==n){
            cout << dp[a][b];
            return 0;
        }
        ll da[3]={a,a+b,a-1}, db[3]={a,b,b};
        for(int i=0; i<3; i++){
            if(0>=da[i] || da[i]>2*n) continue;
            if(dp[da[i]][db[i]]) continue;
            q.push({da[i],db[i]});
            dp[da[i]][db[i]] = dp[a][b] + 1;
        }
    }
}

3. 저울 (Gold 3)

www.acmicpc.net/problem/10159

10159번: 저울

골드 3 치고는 엄청 쉬운 문제이다.

N<=100이므로 그냥 단순한 플로이드 워셜을 이용하면 된다.

그냥 연결된 여부만 보므로 더 쉽다.

#include <bits/stdc++.h>
#define MEM 155
#define sanic ios_base::sync_with_stdio(0)
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pi;
const ll MOD = 1e9+7;
ll n,m,k;
ll dp[MEM][MEM];
queue<pi> q;
main() {
    sanic;
    cin >> n >> m;
    for(int i=0; i<m; i++){
        ll q1, q2;
        cin >> q1 >> q2;
        dp[q1][q2] = 1;
    }
    for(int i=1; i<=n; i++)
        dp[i][i] = 1;
    for(int k=1; k<=n; k++){
        for(int i=1; i<=n; i++){
            for(int j=1; j<=n; j++){
                if(!dp[i][j] && dp[i][k] && dp[k][j])
                    dp[i][j] = 1;
            }
        }
    }
    for(int i=1; i<=n; i++){
        ll cnt=0;
        for(int j=1; j<=n; j++)
            if(dp[i][j] || dp[j][i]) cnt++;
        cout << n-cnt << '\n';
    }
}

 

아슬아슬하게 11분 남기고 다 풀었다.

마지막 문제가 골드 3 치고는 아주 쉬웠으나 빠르게 푼 거 같아서 기쁘다.

실력이 느는 느낌이 많이 든다. 더 열심히 하자.

스코어보드