프로그래밍

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

[난이도] Gold5
[유형] DP

[풀이]

DP[i][0] : 2xi 개의 칸이 전부 차있는 타일 조합의 수
         예시(i=4)   ....
                     ....
DP[i][1] : (1,i) 칸을 제외한 2xi-1 개의 칸이 모두 차있는 타일 조합의 수
         예시(i=4)   ...
                     ....
DP[i][2] : (2,i) 칸을 제외한 2xi-1 개의 칸이 모두 차있는 타일 조합의 수
         예시(i=4)   ....
                     ...

점화식 및 생성 원리는 다음과 같습니다.
dp[i][0]=(2*dp[i-1][0]+dp[i-1][1]+dp[i-1][2]+dp[i-2][0])%m;
    => 0번 모양의 2x(i-1) 타일에서 2x1 타일 1개 또는 1x1 타일 2개를 더해 0번 모양의 2xi 타일을 만들 수 있으므로
       2*dp[i-1][0]
    => 1,2번 모양의 2x(i-1) 타일에서 1x2 타일 1개와 1x1 타일 1개를 더해 0번 모양의 2xi 타일을 만들 수 있으므로
       dp[i-1][1]+dp[i-1][2]
    => 0번 모양의 2x(i-2) 타일에서 1x2 타일 2개를 더해 0번 모양의 2xi 타일을 만들 수 있으므로
       dp[i-2][0]

dp[i][1]=dp[i-1][0]+dp[i-1][2];
    => 0번 모양의 2x(i-1) 타일에서 1x1 타일 1개를 더해 1번 모양의 2xi 타일을 만들 수 있으므로
       dp[i-1][0]
    => 2번 모양의 2x(i-1) 타일에서 1x2 타일 1개를 더해 1번 모양의 2xi 타일을 만들 수 있으므로
       dp[i-1][2]

dp[i][2]=dp[i-1][0]+dp[i-1][1];
    => 0번 모양의 2x(i-1) 타일에서 1x1 타일 1개를 더해 2번 모양의 2xi 타일을 만들 수 있으므로
       dp[i-1][0]
    => 1번 모양의 2x(i-1) 타일에서 1x2 타일 1개를 더해 2번 모양의 2xi 타일을 만들 수 있으므로
       dp[i-1][2]

최종 답은 직사각형 모양의 2xN 타일의 개수이므로 dp[N][0]을 출력해주면 됩니다.

#include <cstdio>
using ll = long long;
int N;
ll dp[1000001][3],m=1000000007;
int main(){
    scanf("%d",&N);
    dp[1][0]=2;
    dp[0][0]=dp[1][1]=dp[1][2]=1;
    for(int i=2;i<=N;i++){
        dp[i][0]=(2*dp[i-1][0]+dp[i-1][1]+dp[i-1][2]+dp[i-2][0])%m;
        dp[i][1]=dp[i-1][0]+dp[i-1][2];
        dp[i][2]=dp[i-1][0]+dp[i-1][1];
    }
    printf("%lld",dp[N][0]);
}

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold5/14852.cpp

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

[난이도] Gold5
[유형] DP

[풀이]
DP[t][w][k] : 현재 t초이며 w만큼 움직였고 k 위치에 있을 때 얻을 수 있는 최대 자두 개수.

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int T,W,a[1001],dp[1001][31][2];
int sol(int t,int w,int k){
    if(t>T) return 0;
    int& ret = dp[t][w][k];
    if(ret!=-1) return ret;
    ret = (k==a[t]) + sol(t+1,w,k);
    if(w<W) ret = max(ret,(k!=a[t]) + sol(t+1,w+1,!k));
    return ret;
}
int main(){
    scanf("%d%d",&T,&W);
    for(int i=1;i<=T;i++) {
        scanf("%d",&a[i]);
        a[i]--;
    }
    memset(dp,-1,sizeof(dp));
    printf("%d",sol(1,0,0));
}

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold5/2240.cpp

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

[난이도] Gold5
[유형] 구현

[풀이]
어떤 행 i,j가 K번 스위치를 눌렀을 때 두 행 모두 켜져있는 상태가 되려면
i,j 행은 초기 상태가 같아야 합니다.
왜냐하면 어떤 열 m의 초기 상태가 달라 lamp[i][m] != lamp[j][m] 상태인 경우
m번 열의 스위치를 아무리 눌러도 lamp[i][m]과 lamp[j][m] 는 동시에 바뀌기 때문에
계속 lamp[i][m] != lamp[j][m] 상태일 수밖에 없습니다.

그러므로 K번 스위치를 눌러서 켜진 상태(모든 열이 1인 상태)를 만들 수 있는
행 i에 대해서 i행과 같은 초기상태를 가지는 행 j의 개수를 구해주면 됩니다.
이 값을 모든 i에 대해 구해주면서 최댓값을 업데이트 해주면서 나온 최종 값이 정답이 됩니다.

K번 스위치를 눌러서 켜진 상태를 만들 수 있는지는
0의 개수가 K보다 작으면서, 0의 개수를 2로 나눈 나머지와 K를 2로 나눈 나머지가 같아야 합니다.

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
int N,M,K,ans;
string lamp[50];
int main(){
    cin >> N >> M;
    for(int i=0;i<N;i++) cin >> lamp[i];
    cin >> K;
    for(int i=0;i<N;i++){
        auto s = lamp[i];
        int cnt=0;
        for(int j=0;j<M;j++) if(s[j]=='0') cnt++;
        if(cnt > K || cnt%2 != K%2) continue;
        int sameCnt=0;
        for(int j=0;j<N;j++) if(s==lamp[j]) sameCnt++; 
        ans=max(ans,sameCnt);
    }
    printf("%d",ans);
}

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold5/1034.cpp

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

[난이도] Gold5
[유형] 구현

[풀이]
오븐의 지름이 넓을 수록 피자를 넣기에 유리하지만 오븐 아래층의 지름이 아무리 넓어도
윗 층의 지름이 더 좁다면 윗 층 지름중 가장 좁은 지름만큼의 넓이를 가진 피자밖에 담을 수가 없습니다.
이를 이용해 O(N) 시간에 문제를 해결할 수 있습니다.

a 배열을 선언하여 다음과 같이 정의합니다.
a[i] : 1~i 층까지의 지름 중 가장 좁은 지름

점화식은 다음과 같습니다. 일종의 메모제이션입니다.
a[i] = min(i번 층의 지름,a[i-1])

이런 식으로 저장하게 되면 a 배열은 내림차순 형태를 띄게 됩니다.

이제 피자를 순서로 입력받으면서
D층부터 넣을 수 있는 곳에 차례대로 채워가면 됩니다.
모든 피자를 넣을 수 없는 경우 0을 출력해야 하는 것을 주의해야 합니다.

#include <cstdio>
#include <algorithm>
using namespace std;
int D,N,a[300001];
int main(){
    scanf("%d%d",&D,&N);
    for(int i=0;i<=D;i++) a[i]=2e9;
    for(int i=1;i<=D;i++) {
        int v;
        scanf("%d",&v);
        a[i] = min(v,a[i-1]);
    }
    int cur=D, ans=0;
    while(N--){
        int v;
        scanf("%d",&v);
        for(;cur>=0;cur--){
            if(v<=a[cur]){
                ans=cur;
                cur--;
                break;
            }    
        }
    }
    printf("%d",ans);
}

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold5/1756.cpp

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

[난이도] Gold5
[유형] DP

[풀이]
다이나믹 프로그래밍을 이용해서 해결 할 수 있습니다.

DP[i] : i번 학생까지 조에 포함시켰을 때, 조가 잘 짜여진 정도의 최댓값

위와 같이 정의하면 점화식은 다음과 같습니다.
DP[i] = DP[j] + maxv:(1~j 중 최댓값) - minv:(1~j 중 최솟값) (0<=j<=i-1)

i번 학생을 1~i 번 학생이 있는 조, 2~i번 학생이 있는 조, ... i~i번 학생이 있는 조 (조에 i번 혼자인 경우)
에 포함시켜 보면서 그 중 최댓값을 DP[i]로 업데이트 하는 방식입니다.

#include <cstdio>
#include <algorithm>
using namespace std;
int N,dp[1001],a[1001];
int main(){
    scanf("%d",&N);
    for(int i=1;i<=N;i++) scanf("%d",&a[i]);
    for(int i=2;i<=N;i++){
        int minv=a[i],maxv=a[i];
        for(int j=i-1;j>=0;j--){
            maxv=max(a[j+1],maxv);
            minv=min(a[j+1],minv);
            dp[i] = max(dp[i],dp[j]+maxv-minv);
        }
    }
    printf("%d",dp[N]);
}

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold5/2229.cpp

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

[난이도] Gold5
[유형] DP

[풀이]
DP[i] = DP[i-1] + DP[i-2]*2 점화식을 이용해 모든 코드의 개수를 구할 수 있습니다.

이미 좌우 대칭인 코드를 제외한 모든 코드는 자신과 대칭이 되는 코드를 가지고 있습니다.
이미 좌우 대칭인 코드의 개수를 t라고 했을 때,
최종 정답은 (DP[N]-t)/2 + t 가 됩니다.
그 이유는 DP[N]-t 가 자신과 대칭이 되는 코드를 가지고 있는 코드들의 개수이므로
중복 제거를 위해 이것을 2로 나누어 주면 중복이 제거되기 때문입니다.
여기에 다시 좌우 대칭인 코드의 개수인 t를 더해줌으로써 최종 답이 됩니다.

t를 구하는 방법은 홀수와 짝수인 경우가 달라집니다.
홀수인 경우 좌우 대칭이려면 가운데 무조건 2x1 타일이 있어야 하므로
t = DP[N/2] 가 됩니다.

짝수인 경우에는 중앙에 2x1 타일 두개, 2x2 타일 한개가 위치하고, 이를 중심으로 대칭인 경우도
추가해 주어야 하므로
t = DP[N/2] + 2*DP[N/2-1] 이 됩니다.

#include <cstdio>
int N,dp[31];
int main(){
    scanf("%d",&N);
    dp[1]=dp[0]=1;
    for(int i=2;i<=N;i++) dp[i]=dp[i-1]+dp[i-2]*2;
    int t=dp[N/2];
    if(N%2==0) t+=2*dp[N/2-1];
    printf("%d",(dp[N]-t)/2+t);
}

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold5/1720.cpp

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

[난이도] Gold5
[유형] 스택

[풀이]
이 문제와 같이 여는괄호 닫는괄호가 나오면 보통 stack을 활용하여 푸는 문제입니다.
stack<char> 형태의 char형을 저장하는 스택을 선언하여 실제로 압축을 해제하며 저장하면
메모리 초과가 발생하게 됩니다.
stack<int>형 스택을 선언하여 문자열의 실제 길이를 int 값으로 저장해주어야 합니다.

풀이는 다음과 같습니다.

문자열을 앞에서부터 순회하면서
  i) '(' 인 경우
    '('를 숫자와 구분하기 위해 절대 나올 수 없는 수인 -1을 push 해줍니다.

 ii) 숫자인 경우
    뒤의 문자가 '('인 경우 문자의 길이를 곱할 때 사용해야 하므로 숫자 그대로 스택에 push 해줍니다.
    그 외의 경우에는 어떤 숫자이든 결국 문자열의 길이로는 1의 가치가 있기 때문에 1을 push 해줍니다.

iii) ')' 인 경우
    스택의 top이 '(' (즉, -1) 일 때까지 pop하며 len에 더해준 뒤,
    '(' 를 pop 한 뒤의 top과 곱해준 뒤 한번 더 pop을 해줍니다.
    예를 들어, 3(1111) 인 경우 (1+1+1+1)*3을 해주라는 의미입니다.
    이 숫자를 다시 stack에 push하여 다음 연산에 사용합니다.

위 과정을 완료 한 뒤 stack의 모든 정수를 더해주면 최종 정답이 됩니다.

#include <string>
#include <iostream>
#include <stack>
#include <vector>
#include <cctype>
using namespace std;
string s;
int main(){
    cin >> s;
    stack<int> st;
    for(int i=0;i<s.size();i++){
        if(s[i]=='(') st.push(-1);
        else if(isalnum(s[i])){
            if(i<s.size()-1 && s[i+1]=='(') st.push(s[i]-'0');
            else st.push(1);
        }else{
            int len=0;
            while(st.top()!=-1) {
                len+=st.top();
                st.pop();
            }
            st.pop();
            len*=st.top(); st.pop();
            st.push(len);
        }
    }
    int ans=0;
    while(!st.empty()){
        ans+=st.top();
        st.pop();
    }
    printf("%d",ans);
}

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold5/1662.cpp

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

[난이도] Gold5
[유형] Greedy

[풀이]
음수인 좌표와 양수인 좌표를 각각 a,b vector에 저장한 뒤 따로 생각해줍니다.
가까운 위치에 있는 좌표부터 M개씩 책을 가져다 놓으면 됩니다.
만약 vector의 크기가 아래와 같이 M으로 나누어 떨어지지 않는다면
아래와 같이 5%2 = 1 번째 책부터 옮겨주면 됩니다.
왜냐하면 가까운 곳을 먼저 왕복해 주는것이 유리하기 때문입니다.

(M==2)
0      0+M     0+2M
-6 -28 -29 -37 -39

위와 같이 옮기면 6*2+29*2+39*2 = 158 이 됩니다.

  M
2 11
좌표가 양수인 크기 2 벡터는 위와 같이 M번째만 방문하면 두 책을 모두 옮길 수 있으므로
11*2=22 이 됩니다.

여기서 마지막으로 책을 가져놓은 좌표에서 다시 0으로 돌아오지 않아도 되므로
0에서 가장 먼 좌표가 포함되어 있는 음수 vector를 나중에 처리하는 것이 유리합니다.
그러므로 -39 좌표의 책을 옮긴 뒤에 0으로 돌아오는 것은 고려하지 않아도 되므로
158+22-39 = 131이 최종 정답이 됩니다.

#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
int N,M;
vector<int> a,b;
int main(){
    scanf("%d%d",&N,&M);
    for(int i=0;i<N;i++) {
        int v;
        scanf("%d",&v);
        if(v>0) a.push_back(v);
        else b.push_back(-v);
    }
    sort(a.begin(),a.end());
    sort(b.begin(),b.end());
    int ans=0;
    if(!a.empty()){
        for(int i=a.size()%M-1;i<(int)a.size();i+=M){
            if(i>=0) ans+=a[i]*2;
        }
    }
    if(!b.empty()){
        for(int i=b.size()%M-1;i<(int)b.size();i+=M){
            if(i>=0) ans+=b[i]*2;
        }
    }
    if(a.empty()) ans-=b.back();
    else if(b.empty() || a.back()>b.back()) ans-=a.back();
    else ans-=b.back();

    printf("%d",ans);
}

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold5/1461.cpp