[SRM]#715 Div2

250. ImageCompression

단순구현 문제이다. 입력으로 주어지는 이미지를 k등분했을 때, 등분된 구성성분들이 일치하는지 묻는 문제.

단순 반목문으로 구현가능하다

#include <cstdio>
#include <vector>
#include <string>
#include <iostream>
using namespace std;
 
class ImageCompression
{
public:
    string isPossible(vector<string>image, int k)
    {
        int r = image.size();
        int c = image[0].size();
        for (int i = 0; i < r; i += k)
        {
            for (int j = 0; j < c; j += k)
            {
                char chk = image[i][j];
                for (int a = i; a < i + k; a++)
                {
                    for (int b = j; b < j + k; b++)
                    {
                        if (chk != image[a][b])
                            return "Impossible";
                    }
                }
            }
        }
        return "Possible";
 
    }
};
[출처] TopCoder SRM #715 Div 2 Review|작성자 kimsy96

500. MaximunRangeDiv2

풀이 1: Dp

dp[i][Max][Min][val] : 현재 문자열의 i번째 인덱스를 보았을 때, 최대가 Max고 최소가 Min이고 현재값이 val일때  Max와 Min의 차이

#include <bits/stdc++.h>
using namespace std;
 
string p;
 
int n;
int dp[51][102][102][102];
 
int solve(int i,int Mx,int Mn,int val)
{
    int &ret=dp[i][Mx][Mn][val];
    if(ret!= -1) return ret;
    if(i==n)
        return Mx-Mn;
    ret=solve(i+1,Mx,Mn,val);
    if(p[i]=='+'){
        int nextval=val+1;
        Mx=max(Mx,nextval);
        ret=max(ret,solve(i+1,Mx,Mn,nextval));
    }
    if(p[i]=='-'){
        int nextval=val-1;
        Mn=min(Mn,nextval);
        ret=max(ret,solve(i+1,Mx,Mn,nextval));
    }
    return ret;
}
 
class MaximumRangeDiv2
{
public:
    int findMax(string s)
    {
        p=s;
        n=s.length();
        memset(dp,-1,sizeof(dp));
        return solve(0,50,50,50);
    }
};
 
[출처] TopCoder SRM #715 Div 2 Review|작성자 kimsy96
 
 

풀이 2: Greedy

greedy한 해법도 가능하다고 한다. 아직 그 증명을 완벽히 이해하진 못했지만 훨씬 쉽게 풀 수 있다.

div1 250점 문제도 위와 같은데 입력제한이 훨씬 커서 동적계획법으로 풀 수 없다. 그 문제는 그리디 해법으로만 풀 수 있다.

#include <string>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <cstring>
#include <algorithm>
using namespace std;
 
class MaximumRangeDiv2
{
public:
    int findMax(string s)
    {
        int plus = 0;
        int minus = 0;
        for (int i = 0; i < s.length(); i++) {
            if (s[i] == '+')
                plus++;
            else
                minus++;
        }
        return max(plus, minus);
    }
};
[출처] TopCoder SRM #715 Div 2 Review|작성자 kimsy96