오늘의 문제 2020.5.18

이 그룹 에서 매일 문제를 푼다.

2020.5.18

 A - 피보나치 수 5

10870번: 피보나치 수 5

어떻게 푸는지 아시죠??

 

B - 정사각형

1485번: 정사각형

이것도 다 아실거라 믿습니다. (못풀면 공부하고 오세요!)

 

C - 효율적인 해킹

1325번: 효율적인 해킹

간선을 $u$ $v$ 로 입력받으면 $v$ -> $u$ 로 가는 간선을 만든다.

그러면 우린 한 정점에서 시작해서 갈 수 있는 모든 정점의 개수가 해킹할 수 있는 최대 컴퓨터 수 가 된다!

그래서 이걸 구현해 주면 된다.

 

#include <bits/stdc++.h>
using namespace std;
int c[10005],cnt[10005],co = 1;
vector <int> v[10005];
vector <int> ans[10005];
int n,m;

int dfs(int edge)
{
    if(c[edge] == co) return 0;
    c[edge] = co;
    int sum = 1;
    for(int i = 0;i < v[edge].size();i++)
    {
        sum += dfs(v[edge][i]);
    }
    return sum;
}

int main()
{
    scanf("%d %d", &n, &m);
    for(int i = 1;i <= m;i++)
    {
        int x,y;
        scanf("%d %d", &x, &y);
        v[y].push_back(x);
    }
    int ap = 0;
    for(int i = 1;i <= n;i++)
    {
        cnt[co] = dfs(i);
        if(cnt[ap] < cnt[co]) ap = co;
        co++;
    }
    for(int i = 1;i <= n;i++)
    {
        if(cnt[i] == cnt[ap]) printf("%d ",i);
    }
    return 0;
}

 

D - 신기한 키보드

1796번: 신기한 키보드

'a' 부터 'z' 까지 차례대로 출력을 하면 되는게 목표인데, 무조건 어떤 문자가 나온 장소중 가장 왼쪽, 가장 오른쪽 모두 지나야 한다는 것을 알 수 있다.

 

$l[x]$ : $x$번째 문자가 나타나는 위치중 제일 왼쪽 위치

$r[x]$ : $x$번째 문자가 나타나는 위치중 제일 오른쪽 위치

$go(x,wh)$ : $x$번째 문자를 출력해야 하고, 지금 위치가 $wh$일때 최소 움직임 횟수

그러면 구하고자 하는 답은 $go(1,1)+n$ 가 된다.

 

그러면 우리가 $x$라는 위치에 서 있다고 하면, $l[x]$ 로 갔다가 $r[x]$으로 가는 경우와, $l[x]$ 로 갔다가 $r[x]$으로 가는 경우가 있다. 각각의 경우에 대해 모든 경우를 다해보면, 답이 나온다.

시간복잡도는 $O(2^{26})$ 가 된다.

 

참고로 동적 계획법을 이용하면 $O(26n)$ 시간으로 줄일 수 있고, 위치를 나타내는 것을 $[2]$, 즉 왼쪽에서 끝났냐, 오른쪽에서 끝났냐만 가지고 하면, $O(52)$ 만에 가능하기도 한다.

 

#include <bits/stdc++.h>
using namespace std;
vector <int> al[30];
int l[30],r[30];
int n;
int d[30][1005];
char s[1005];

int go(int x,int now)
{
    if(x == 27) return n;
    if(l[x] == 0&&r[x] == 0) return go(x+1,now);
    if(l[x] == r[x]) return go(x+1,l[x])+abs(now-l[x]);
    return min(go(x+1,l[x])+abs(r[x]-now),go(x+1,r[x])+abs(l[x]-now))+abs(r[x]-l[x]);
}

int main()
{
    memset(d,-1,sizeof(d));
    cin >> s+1;
    n = strlen(s+1);
    for(int i = 1;i <= n;i++) al[s[i]-'a'+1].push_back(i);
    for(int i = 1;i <= 26;i++)
    {
        if(al[i].size() == 0) continue;
        l[i] = al[i][0],r[i] = al[i][al[i].size()-1];
    }
    cout << go(1,1);
}

 

E - LCS 3

1958번: LCS 3

$LCS$문제를 풀어봤으면 이 문제도 풀 수 있다.

$DP[i][j][k]$ : 첫번째 문자열은 $i$자리, 두번째 문자열은 $j$자리, 세번째 문자열은 $k$자리까지 봤을 때 가능한 최대 $LCS$ 길이 

 

라고 두면 우리가 두 문자열 $LCS$ 했던 것처럼 똑같이 해줄 수 있다.

 

#include <bits/stdc++.h>
using namespace std;
char a[105],b[105],c[105];
int ap,bp,cp,d[105][105][105];

int main()
{
    cin >> a >> b >> c;
    ap = strlen(a);
    bp = strlen(b);
    cp = strlen(c);

    for(int i = 1;i <= ap;i++)
    {
        for(int j = 1;j <= bp;j++)
        {
            for(int k = 1;k <= cp;k++)
            {
                if(a[i-1] == b[j-1]&&b[j-1] == c[k-1]) d[i][j][k] = d[i-1][j-1][k-1]+1;
                d[i][j][k] = max(max(d[i][j][k],d[i-1][j][k]),max(d[i][j-1][k],d[i][j][k-1]));
            }
        }
    }
    cout << d[ap][bp][cp];
}

 

F - 팰린드롬??

11046번: 팰린드롬??

$N=1000$ 인 경우일때 하는 문제인 줄 알고 출제를 했지만... 알고보니 $N=1000000$ 이였다!

마나커 알고리즘을 알아야 하는데, 딱히 알 필요는 없다.

 

그러니 이 문제는 풀이를 생략하겠다! (도움 안됨 ㅠ)

 

G - 분할하기

18184번: 분할하기

아이디어성 문제다! 드디어 괜찮은 문제가 나왔어!

 

한가지 관찰을 해보면, $k$제한이 없으면 모든 수의 비트를 반전 시켜도 답이 된다.

이 관찰이 매우 어렵다... (그래서 플4다!)

 

그리고 우린 사용할 숫자를 체크 배열에 체크해줄 것이다.

 

일단 $k=2^{n}$ 이라면 그냥 $0~k-1$ 을 체크해주면 된다.

$2^{n-1} \geq k$ 라면 $2^{n}$번째 비트를 사용하지 않고, n을 감소시켜 준다. ($2^{n}$비트를 사용하지 않는다는 말이다.)

$2^{n-1} < k$ 라면 $n-1$, $k-2^{n-1}$ 에 대한 답을 구해준뒤, 체크 배열을 뒤집어 준다.

 

풀때만 해도 아~! 하고 이해하면서 풀었지만, 4개월이 지난 지금은 풀이가 잘 가물가물하다...

진정한 고수라면 나의 노답 풀이를 듣고도 이해할 수 있을 것이다...

나중에 풀이가 갑자기 이해가 된다면 포스팅을 해보겠다!

 

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
vector <int> ans;
int c[5005];

void go(int n,int k) {
    //cout << n << " " << k << '\n';
    if(k == (1 << n)) {
        for(int i = 0;i < k;i++) {
            c[i] = 1;
        }
        return;
    }
    if((1 << (n-1)) >= k) {
        go(n-1,k);
    }
    else {
        go(n-1,(1 << n)-k);
        for(int i = 0;i < (1 << n);i++) {
            c[i] = 1-c[i];
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0);
    int n,k;
    cin >> n >> k;
    cout << "YES\n";
    go(n,k);
    for(int i = 0;i < (1 << n);i++) {
        if(c[i]) cout << i << " ";
    }
    return 0;
}