오늘의 문제 2020.5.20

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

| 오늘의 문제 |

2020.5.20

 

 A - 1998년생인 내가 태국에서는 2541년생?!

18108번: 1998년생인 내가 태국에서는 2541년생?!

푸실 수 있죠?

 

B - 2차원 배열의 합

2167번: 2차원 배열의 합

브루트 포스

 

C - 다음 순열

10972번: 다음 순열

 

next_permutation(a,a+n) 

끝.

 

D - 이전 순열

10973번: 이전 순열

 

prev_permutation(a,a+n)

끝.

 

E - 모든 순열

10974번: 모든 순열

do {
	print(a)
} while(next_permutation(a,a+n));

끝.

 

F - 용액

2467번: 용액

알고리즘 : 투 포인터

오름차순 정렬 후 포인터를 \(l\), \(r\) 두개를 잡아서 \(l\)은 \(1\), \(r\)은 \(n\)으로 둔다.

\(a[l]+a[r] < 0\) 이라면 \(l\) 한칸 전진

\(a[l]+a[r] \geq 0\) 이라면 \(r\) 한칸 전진 하면서

각 진행 상황에 대해 \(|a[l]+a[r]|\) 최솟값 저장.

\(l \geq r\) 이 되기 전까지 반복.

끝난 후 정답이 되는 \(l\), 정답이 되는 \(r\) 출력

 

 
#include <bits/stdc++.h>
using namespace std;
int a[100001];
 
int abs(int x){return x > 0 ? x : -x;}
 
int main(){
    int n;
    scanf("%d", &n);
    for (int i = 0;i < n;i++)
    {
        scanf("%d",&a[i]);
    }
    sort(a,a+n);
    int left = 0,right = n - 1,ans = 2000000001;
    int l = 0,r = 0;
    while(left < right)
    {
        int sum = a[left] + a[right];
        if(abs(sum) < ans)
        {
            ans = abs(sum);
            l = left;
            r = right;
            if(ans == 0) break;
        }
        if(sum < 0) left++;
        else right--;
    }
    printf("%d %d",a[l],a[r]);
}
 

 

G - 사과와 바나나

3114번: 사과와 바나나

알고리즘 : 동적 계획법

\(DP[i][j]\) : 불도저가 \(i\)번째 열 \(j\)번째 행 지점에 있을때 가능한 최대 조건을 충족하는 과일 수.

라고 두면

\(DP[i][j] = max(DP[i-1][j]+Sum(B[i][1]~B[i][j]),DP[i][j-1]+B[i][j]-A[i][j])\) 가 됨을 알 수 있다.

 

H - 가장 긴 증가하는 팰린드롬 부분수열

16161번: 가장 긴 증가하는 팰린드롬 부분수열

헤헤 나도 어떻게 풀지 모른다.

 

I - 두 번 뒤집기

2505번: 두 번 뒤집기

뒤집어야 할 구간을 두개 구해줘야 한다.

일단 왼쪽부터 가면서 자신의 위치랑 원래 있어야 할 숫자가 다른지 본다. ($i$번째 위치라 하자)

다르다면, \(i\)가 배열에 어디있는지 찾는다. 그러면 처음 뒤집을 구간이 정해졌다!

뒤집고 나면, 어딘가 또 안되는 부분이 있을 것이다. 그것도 똑같이 찾아준다.

만약 완성이 되었다면 1~1 구간을 뒤집어 준다. (횟수 날리기)

 

근데 이렇게 하면 불가능 한 경우가 있다.

그래서 오른쪽 부터 보는 것도 해봐야 한다.

똑같은 방법으로 진행한다.

 

코드가 조금 드러우니 보지 않는걸 추천한다.

 

#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair <ll,ll> pl;
typedef pair <int,int> pi;
int n;
int a[10005];
int st,en;
vector <pi> ans;

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0);
	cin >> n;
	for(int i = 1;i <= n;i++) {
		cin >> a[i];
	}
	st = 0;
	for(int i = 1;i <= n;i++) {
		if(a[i] != i) {
			st = i;
			for(int j = 1;j <= n;j++) {
				if(a[j] == i) {
					en = j; break;
				}
			}
			break;
		}
	}
	if(st > en) swap(st,en);
	if(!st) st = 1, en = 1, ans.push_back({1,1});
	else ans.push_back({st,en});
	reverse(a+st,a+en+1);
	st = 0;
	en = 0;
	for(int i = 1;i <= n;i++) {
		if(a[i] != i) {
			st = i;
			for(int j = 1;j <= n;j++) {
				if(a[j] == i) {
					en = j; break;
				}
			}
			break;
		}
	}
	if(st > en) swap(st,en);
	if(!st) st = 1, en = 1, ans.push_back({1,1});
	else ans.push_back({st,en});
	reverse(a+st,a+en+1);
	int c = 0;
	for(int i = 1;i <= n;i++) {
		if(a[i] != i) {
			c = 1;
			break;
		}
	}
	if(!c) {
		cout << ans[0].x << ' ' << ans[0].y << '\n' << ans[1].x << ' ' << ans[1].y << '\n';
		return 0;
	}
	reverse(a+ans[1].x,a+ans[1].y+1);
	reverse(a+ans[0].x,a+ans[0].y+1);

	ans.clear();
	st = 0;
	for(int i = n;i >= 1;i--) {
		if(a[i] != i) {
			st = i;
			for(int j = 1;j <= n;j++) {
				if(a[j] == i) {
					en = j; break;
				}
			}
			break;
		}
	}
	if(st > en) swap(st,en);
	if(!st) st = 1, en = 1, ans.push_back({1,1});
	else ans.push_back({st,en});
	reverse(a+st,a+en+1);
	st = 0;
	en = 0;
	for(int i = n;i >= 1;i--) {
		if(a[i] != i) {
			st = i;
			for(int j = 1;j <= n;j++) {
				if(a[j] == i) {
					en = j; break;
				}
			}
			break;
		}
	}
	if(st > en) swap(st,en);
	if(!st) st = 1, en = 1, ans.push_back({1,1});
	else ans.push_back({st,en});
	reverse(a+st,a+en+1);
	cout << ans[0].x << ' ' << ans[0].y << '\n' << ans[1].x << ' ' << ans[1].y << '\n';
} 

 

J - 2,3 거듭제곱의 합

2727번: 2,3 거듭제곱의 합

이번 셋에서 내가 제일 좋아하는 문제다.

진짜 하나만 생각하면 풀리는 것이다.

우린 3을 사용하지 않는다. 정확히 말하면 3의 지수는 모두 0으로 사용할 것이다.

그러면... 우린 2의 제곱수만을 가지고 어떤 수 $x$를 만들라는 문제가 된다.

$x$를 이진 수로 표현해보면 나타나는 1의 위치를 출력하면 된다.

 

문제를 제대로 읽지 않고 풀었지만, 스페셜 저지가 이상해 맞은것으로 처리되었습니다.

현재는 정상적으로 수정되었고 위의 풀이는 틀린 풀이입니다.

 

#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair <ll,ll> pl;
typedef pair <int,int> pi;
ll x,T;
vector <ll> ans;

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0);
	cin >> T;
	while(T--) {
		ll n; cin >> n; ans.clear();
		x = 0;
		while(n) {
			if(n%2) ans.push_back(x);
			x++; n /= 2;
		}
		cout << ans.size() << '\n';
		for(ll i : ans) cout << i << " 0\n";
	}
}

 

K - 세 번 뒤집기

2561번: 세 번 뒤집기

능지가 딸려서 못풀었다.