ALOHA 초급반 5주차 연습 후기

All Solve는 성공했습니다! 
5번하고 6번에서 조금 애먹었네요

 

1. Fibonacci Number 2
https://www.acmicpc.net/problem/2748

2748번: 피보나치 수 2

피보나치 수의 기본 점화식
f(n) = 0 (if n==0)
     = 1 (if n==1)
     = f(n-1) + f(n-2) (n>=2)
를 사용하면 간단하게 풀리는 문제입니다. 
주의해야할 점은 C/C++의 경우 long long int자료형을 사용하지 않고 그냥 int형을 사용할 경우 overflow로 인해 틀리게 됩니다.

#include <stdio.h>

long long int fibo[95];

int main(){
    fibo[0]=0;
    fibo[1]=1;
    fibo[2]=1;
    for(int i=3; i<=90; i++){
        fibo[i] = fibo[i-1] + fibo[i-2];
    }
    int n;
    scanf("%d", &n);
    printf("%lld", fibo[n]);
}

2. 이항 계수 2
https://www.acmicpc.net/problem/11051

11051번: 이항 계수 2

 

이항 계수와 파스칼의 삼각형의 성질을 사용하면 됩니다. 
nCk 는 파스칼의 삼각형에서 n번째줄의 k번째 항을 의미합니다.
그리고 파스칼의 삼각형의 성질에 따라 nCk = n-1Ck + n-1Ck-1 로 정의됩니다.
여기서 주의해야 할점은 nC0과 nCn은 모든 n번째 줄에 대하여 1이므로 따로 예외 처리를 해줘야 합니다.

#include <stdio.h>

long long int pascal[1005][1005];

int main(){
    int n, k;
    scanf("%d %d", &n, &k);
    for(int i=1; i<=n; i++){
        for(int j=0; j<=i; j++){
            if(j==0 || j==i) pascal[i][j] = 1;
            else{
                pascal[i][j] = (pascal[i-1][j] + pascal[i-1][j-1])%10007;
            }
        }
    }
    printf("%lld", pascal[n][k]);
}

 

3. 가장 긴 증가하는 부분 수열

https://www.acmicpc.net/problem/11053

11053번: 가장 긴 증가하는 부분 수열

 

개인적으로 이게 왜 실버 2 밖에 안되는지 모르겠습니다... 위에 있는 이항 계수 문제보다 구현도 떠올리기 어렵고 직관적으로 이해하기도 어려운데... (저거는 실버 1인데...) 아무튼 그렇다니까 그런가보죠 :+1:

일단 이 문제는 n이 1000이하로 제한되어 있어서 O(n^2) 풀이가 가능합니다. 더 효율적인 O(n log n) 풀이가 존재하지만 여기서는 다루지 않겠습니다.

 

일단 예제 입출력에서 한가지 알아차릴수 있는게 있는데 이 문제에서 의미하는 부분 수열은 연속된 수열만을 의미 하지 않습니다. 즉 어떤 수 이전에 어떤 위치에서든 더 작은 수가 존재했다면 그 두 수는 증가하는 부분 수열을 이룹니다.

따라서 해당 문제는 이렇게 접근 가능합니다.
우선 배열 하나를 (이름은 lis) 정의 할건데 이 배열의 정의에서
lis[n] = (n번째 수로 끝나는 최장 증가 부분 수열의 길이) 입니다.

 

그리고 모든 n번째 수에 대해 lis[n]를 1로 초기화 시켜줄겁니다 (모든 수는 동시에 길이 1의 증가 부분 수열이기도 합니다)

이제 0번째에서 n-1번째 까지 수를 한번씩 고정 시켜놓을건데 이를 i번째 수로 잡아둡시다.
그리고 j를 0에서 n-1까지 반복문을 돌리면서 수열의 j번째 수와 i번째 수에 대해 다음을 확인해줄겁니다.

    1) j번째 수가 i번째 수보다 작다면 
    2) lis[i] = (lis[i]와 lis[j]+1중에 더 큰 값)]

 

이유는 간단합니다. i번째 수가 j번째 수보다 크다면 이는 i번째 수와 j번째 수는 증가 부분 수열을 이룬다는 뜻이고.
이는 추가적으로 i번째 수와 j번째 수로 끝나는 모든 증가 부분 수열은 증가 부분 수열을 이룬다는 의미입니다.

그리고 우리는 lis[n]을 n번째 수로 끝나는 최장 증가 부분 수열의 길이로 정의했습니다. 즉 lis[j]는 j번째 수로 끝나는 최장 증가 부분 수열이라는 뜻이죠. 따라서 i번째 수로 끝나는 최장 부분 증가 수열은 자동적으로 lis[j]+1 또는 (이미 lis[i]가 lis[j]보다 큰 경우) lis[i]입니다.

#include <bits/stdc++.h>
using namespace std;

int arr[1005];
int lis[1005];
int ans;

int main(){
    int n;
    cin >> n;
    for(int i=0; i<n; i++) cin >> arr[i];
    for(int i=0; i<n; i++){
        lis[i] = 1;
        for(int j=0; j<n; j++){
            if(arr[j]<arr[i]){
                lis[i] = max(lis[i], lis[j]+1);
            }
            ans = max(ans, lis[i]);
        }
    }
    cout << ans;
}

 

4. 2xn 타일링 2

https://www.acmicpc.net/problem/11727

11727번: 2×n 타일링 2

 

이거도 솔직히... 절대 실버 3보다는 어렵다 생각합니다...

접근 자체는 간단하니 한번 살펴봅시다.

 

일단 dp[n]을 가능한2xn타일링의 갯수라고 정의합시다.

우리는 모든 n>2인 n에 대해 경우를 딱 세가지로 나눌수 있습니다.

1) 1x2 크기의 직사각형으로 끝나는 경우

2) 2x1 크기의 직사각형 두개로 끝나는 경우

3) 2x2크기의 직사각형으로 끝나는 경우

우선 1)번 경우를 살펴봅시다. 1)번 에 해당하는 2xn타일링은 사실 2x(n-1)타일링에 1x2타일 하나를 끝에 붙여준겁니다. 그러므로 1)번에 해당하는 2xn타일링의 갯수는 2x(n-1)타일링의 갯수와 동일합니다.

2)번과 3)번도 비슷하게 생각하면 2x(n-2)타일링에 각각 2x1 크기의 직사각형 두개와 2x2크기의 직사각형 하나를 끝에 붙여준 형태임을 알수 있습니다. 따라서 각각 2), 3) 에 해당하는 2xn타일링의 갯수는 2x(n-2)타일리의 갯수와 동일합니다.

즉 dp[n]=dp[n-1]+2*dp[n-2] 입니다. 
물론 초항을 두개는 설정해 줘야 하는데 dp[1]=1 dp[2]=3입니다. 이는 종이에 그려보면 쉽게 이유를 알수 있습니다.

 

사실 그런데 풀이를 알고 나니까 간단한거지... 절대 생각해내기 쉬운 문제는 아니라고 봅니다... 일단 이항 계수나 RGB거리 보다는 훨씬 개인적으로 어려웠습니다...

 

한가지 더 주의해야 할점은 각 단계에서 10007로 나눈 나머지를 저장해줘야 합니다. 답을 출력하는 과정에서만 해줄시에는 이미 overflow가 발생한 상태라 답이 틀릴수 있습니다.

#include <bits/stdc++.h>
using namespace std;

int dp[1005] = {0,1,3};

int main(){
    int n;
    cin >> n;
    for(int i=3; i<=1000; i++){
        dp[i] = (2*dp[i-2]+dp[i-1])%10007;
    }
    cout << dp[n];
}

 

5. 파도반 수열

https://www.acmicpc.net/problem/9461

9461번: 파도반 수열

 

수열의 항을 몇개 써보면 n번째 항은 n-2번째 항의 합과 n-3번째 항의 합이라는 걸 알 수 있습니다... 만... 저도 왜 그런지는 잘 모르겠습니다...

오히려 도형 자체의 성질로 생각해본다면 더해서 n번째 삼각형의 한변의 길이를 이루는 두 삼각형이 n-1번째 삼각형과 n-5번째 삼각형임을 알 수 있습니다. 따라서 dp[n]=d[n-1]+dp[n-5] 도 성립합니다. 물론 이 경우에는 초항을 적어도 n=5까지 적어줘야 하지만 문제에 10번째 항까지 주어져 있으니 직접 찾을 필요는 없습니다.

 

dp[n] = dp[n-2]+dp[n-3]이 왜 성립하는지 알게 되면 따로 한번 정리해보도록 하겠습니다...

 

#include <bits/stdc++.h>
using namespace std;

int t;
long long int padovan[105] = {0,1,1,1,2,2};

int main(){
    for(int i=6; i<=100; i++){
        padovan[i] = padovan[i-1] + padovan[i-5];
    }
    cin >> t;
    while(t--){
        int n;
        cin >> n;
        cout << padovan[n] << '\n';
    }
}

6. 극장 좌석

https://www.acmicpc.net/problem/2302

2302번: 극장 좌석

 

가장 먼저 문제에서 받아들여야 할점은 vip좌석은 고정되어 있다는 점입니다. 즉 우리는 좌석의 배치를 vip좌석을 기준으로 구역으로 나눌수 있고 각 구역의 가능한 배치의 경우의 수를 독립적으로 계산해줄수 있다는 것입니다. 

따라서 최종 답은 각 구역의 경우의 수의 곱이 되겠습니다.

 

하지만 그전에 구해줘야 할것이 있는데 바로 (vip가 없을때) 길이 n의 좌석에 대해 가능한 배치 수 입니다.
이것을 미리 계산해주면 각 구역의 길이만 알면 그 구역의 가능한 배치 수를 빠르게 알 수 있기 때문입니다.

vip를 기준으로 구역을 나누었기 때문에 각 구역에는 vip가 들어가지 않는다는것이 보장됩니다. 따라서 vip를 경우의 수에 고려할 필요가 없습니다.

 

따라서 우리는 그것을 dp를 통해 구할것입니다. 
조금 특이하게 여기서 dp[0]을 0으로 정의해줄것입니다. 이는 길이 0인 구간 (vip가 두명 붙어있는 경우) 에 대해 *=dp[0] 를 해주는 경우 답이 틀리지 않기 위한 처리입니다.

 

dp[1]=1 dp[2]=2
그외의 n에 대해 n=3, 4일때를 가지고 설명해 보겠습니다. 

우선 n=1 일때의 배치는
1

n=2일때는
1 2
2 1

n=3일때는 
1 2 3

2 1 3

1 3 2

 

n=4일때는
1 2 3 4
2 1 3 4
1 3 2 4

1 2 4 3
2 1 4 3

 

혹시 보이시나요?

사실 n번째 배치는 n-1번째 배치에 n을 끝에 붙이거나 n-2번째 배치에 n-1과 n이 들어오는 경우입니다.

따라서 dp[n]=dp[n-1]+dp[n-2]입니다.

 

밑에 코드에 좀 이상한 문법(?)들을 사용하기는 했는데 무시해주시고 저 위의 접근에 좀더 집중해 주시기 바라겠습니다...!

(사실 블로그 글쓴이가 코드 다시 쓰기 귀찮아서 그렇습니다 지나가다 보이면 한번씩 혼내줍시다)

 

#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
using namespace std;

int n,m;
long long int ans = 1;
vector<int>vip;
long long int dp[41] = {1,1,2};

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    for(int i=3; i<=40; i++){
        dp[i] = dp[i-1] + dp[i-2];
    }
    cin >> n >> m;
    for(int i=0; i<m; i++){
        int tmp;
        cin >> tmp;
        vip.push_back(tmp);
    }
    int cur=0;
    for(int &i : vip){
        ans *= dp[i-cur-1];
        cur = i;
    }
    ans *= dp[n-cur];
    cout << ans;
}

 

7. 하와와 대학생쨩 하와이로 가는 거시와요~

https://www.acmicpc.net/problem/16456

16456번: 하와와 대학생쨩 하와이로 가는 거시와요~

 

하와와... 제목부터 어지러운 것이와요... 
문제 난이도도 너무 어지러운 것이와요...
출제자를 하와이로 보내버리고 싶었던 것이와요... 하와와...

하와와... 풀이는 그장 좌석과 비슷하게 생각하면 되는 것이와요...

 

우선 n=5 까지 가능한 방문 순서를 적어 볼 것이와요...

 

n=1

1

 

n=2

1 2

 

n=3

1 2 3

1 3 2

 

n=4

1 2 3 4

1 3 2 4

 

1 2 4 3

 

n=5

1 2 3 4 5

1 3 2 4 5

1 2 4 3 5

 

1 2 3 5 4

1 3 2 4 5

 

하와와... 사실 n번째 섬까지 갈 수 있는 방법은 n-1번째 섬에서 한칸 더 가는 방법과 n-2번째 섬에서 두 칸 더 가는 방법인 것이와요... 와타시... 뒤로도 한칸 갈 수 있으니 n-2번째 섬에서 n번째 섬으로 가고 n-1번째 섬으로 후진해도 되는것이와요...

 

여기서도 나머지 연산을 빼먹으면 큰일 날수도 있는 것이와요... 여러분 모두 조심해주시길 바라는 것이와요.. 하와와...

 

#include <bits/stdc++.h>
using namespace std;

const int mod = 1e9+9;
long long int hawawa[50005] = {0,1,1,2};

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    for(int i=4; i<=50000; i++){
        hawawa[i] = (hawawa[i-1]%mod + hawawa[i-3]%mod)%mod;
    }
    int n;
    cin >> n;
    cout << hawawa[n];
}

 

8. 줄세우기

https://www.acmicpc.net/problem/2631

2631번: 줄세우기

 

문제에서 받아들여야 할게 몇가지 있습니다.
1) 저히는 어떤 아이든 우리가 원하는 임의의 위치로 옮길수 있습니다.
2) 우리는 아이들을 오름차순으로 정렬해야 합니다.
3) 우리는 옮기는 횟수가 가장 적게 만들어야 합니다.

이 정보들을 토대로 한가지 중요한 사실을 알 수 있습니다.

오름차순으로 정렬하는 과정에서 우리는 이미 오름차순인 아이들은 고정 시킬수 있습니다.
즉 우리는 아이들로 이루어진 수열중 오름차순이면서 가장 긴것은 유지 시키고 그 외의 아이들은 각자 맞는 위치로 옮겨 주면 최저 횟수로 아이들을 정렬시킬수 있게 됩니다.

"수열중 오름차순이면서 가장 긴것" 즉 가장 긴 증가 부분 수열과 같은 문제가 됩니다. 다만 여기서는 그 수열의 길이가 아닌 아이들을 옮겨야 하는 횟수이므로 (아이들 수)-(수열의 길이)가 답이 됩니다.

 

#include <bits/stdc++.h>
using namespace std;

int arr[1005];
int lis[1005];
int ans;

int main(){
    int n;
    cin >> n;
    for(int i=0; i<n; i++) cin >> arr[i];
    for(int i=0; i<n; i++){
        lis[i] = 1;
        for(int j=0; j<n; j++){
            if(arr[j]<arr[i]){
                lis[i] = max(lis[i], lis[j]+1);
            }
            ans = max(ans, lis[i]);
        }
    }
    cout << n-ans;
}