AtCoder Beginner Contest 196

A. Difference Max

정수 \(a,b,c,d\)에 대해 \(a ≤ x ≤ b, c ≤ y ≤ d\)인 \(x,y\)가 주어질 때, \(x-y\)의 최댓값을 구하는 문제 최댓값은 결국 경계선 값들에 의해 결정되므로 \(a-c, a-d, b-c, b-d\) 중 최댓값을 구하면 된다. (사실 b-c가 답이다.)

#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>
#define endl '\n'
using namespace std;
 
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const ll INF=1e10+1;
 
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    //freopen("input.txt","r",stdin);
    int a,b,c,d;
    cin>>a>>b>>c>>d;
    cout<<max(a-c,max(a-d,max(b-c,b-d)));
    return 0;
}

---

B. Round Down

\(0 ≤ X ≤ 10^{100}\)인 수가 주어지는 데, \(\lfloor X \rfloor\)를 구하는 문제이다. 소수로 입력받지 않고 문자열로 입력받아 소수점 이전까지 출력하면 된다.

#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>
#define endl '\n'
using namespace std;
 
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const ll INF=1e10+1;
 
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    //freopen("input.txt","r",stdin);
    string s;
    cin>>s;
    for(int i=0;i<s.size();i++) {
        if(s[i]=='.') break;
        else cout<<s[i];
    }
    return 0;
}

---

C. Doubled

1부터 \(N\)사이의 자연수에 대해 다음 두 가지 조건을 만족하는 수의 개수를 찾는 문제.

1. 수의 길이는 짝수
2. 수를 절반으로 잘랐을 때, 양쪽의 수가 같은 숫자(예를 들면, 11, 1010, …)

\(N\)의 범위가 \(1 ≤ N ≤ 10^{12}\)이기 때문에 \(O(N)\)의 시간으로 해결 할 수 없다. 그래서 \(N\)을 절반으로 잘라서 확인해야 한다. 양쪽의 숫자가 같아야 하므로 \(N\)의 절반 부분을 a라 하면, aa를 숫자로 변환시켜 N보다 작거나 같은 숫자인지 확인하면 된다.

#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>
#define endl '\n'
using namespace std;
 
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const ll INF=1e10+1;
 
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    //freopen("input.txt","r",stdin);
    ll n;
    cin>>n;
    if(n<9) {
        cout<<0;
        return 0;
    }
    string tmp=to_string(n);
    if(tmp.size()%2==0) tmp=tmp.substr(0,tmp.size()/2);
    else tmp=tmp.substr(0,tmp.size()/2+1); // 길이가 홀수인경우 절반+1까지
    ll lim=stoll(tmp);
    ll ans=0;
    for(ll i=1;i<=lim;i++) { // 절반을 다시 붙여 n보다 작은지 확인
        string t=to_string(i)+to_string(i);
        if(stoll(t)<=n) ans++;
    }
    cout<<ans;
    return 0;
}

---

D. Hanjo

2 X 1 다다미와 1 X 1 다다미를 가지고 HW크기의 방을 덮을 수 있는 경우의 수를 계산하는 문제. dfs로 완전탐색하여 해결할 수 있다. 왜냐하면 방을 덮는 경우의 수는 2 X 1 다다미를 HW 크기의 방을 덮는 수와 같다. 즉, 전체 경우의 수는 \(2^A{HW \choose A}\)이므로 최대 3388이다.

#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>
#define endl '\n'
using namespace std;
 
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const ll INF=1e10+1;

int h, w;
bool used[16][16];
 
ll dfs(int i, int j, int a, int b) {
  if (a<0 || b<0) return 0;
  if (j==w) j=0, i++; // j가 w끝일 때, i+1
  if (i==h) return 1;
  if (used[i][j]) return dfs(i,j+1,a,b); // 이미 사용하고 있다면 다음 칸으로
  ll res=0;
  used[i][j]=1;
  res+=dfs(i,j+1,a,b-1);
  if (j+1<w && !used[i][j+1]) {
    used[i][j+1]=1;
    res+=dfs(i,j+1,a-1,b);
    used[i][j+1]=0;
  }
  if (i+1<h && !used[i+1][j]) {
    used[i+1][j]=1;
    res+=dfs(i,j+1,a-1,b);
    used[i+1][j]=0;
  }
  used[i][j]=0;
  return res;
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    //freopen("input.txt","r",stdin);    
    int a,b;
    cin>>h>>w>>a>>b;
    cout<<dfs(0,0,a,b);
    return 0;
}