이것 저것 &

문제 링크: https://www.acmicpc.net/problem/2437

문제풀이 자체는 정말 쉬운데, 생각하는 과정이 필요했던 문제입니다.

N은 1 이상 1,000 이하이다. 라는 문제 조건을 가진다.

즉 모든 추들을 더하고 빼며 모든경우의 수를 도출(dfs방식)하는 방식으로는 시간 초과를 받을 수밖에 없다.

우선은 누적합 개념에 대해서 이해하셔야 합니다. 

for (int i = 0; i <= n; i++) {
		if (arr[i] > sum + 1) {
			break;
		}
		sum += arr[i];

	}

정렬되어 있는 상태라면 위와 같은 방법으로 O(n) 만에 측정할 수 없는 결과값을 도출할 수 있습니다.

sum은 0부터 시작되며 정렬되어 있는 arr배열에서 가장 작은 값부터 하나씩 증가하며 값을 확인합니다. sum + 1 보다 클 경우 sum + 1에 해당하는 값은 측정할 수 없기 때문에 break를 써서 반복문에서 나가게 되는 구조입니다. 

아래는 정답코드 입니다. 

#include <iostream>
#include <algorithm>
using namespace std;

int n = 0, len = 1;
int arr[1001];
int sum = 0;


int main() {
	cin >> n;
	for (int i = 0; i < n; i++)
		cin >> arr[i];

	sort(arr, arr + n); //오름차순 정렬

	for (int i = 0; i <= n; i++) {
		if (arr[i] > sum + 1) {
			break;
		}
		sum += arr[i];

	}

	cout << sum + 1 << endl;
}

위처럼 간단한 방식으로 정답을 도출할 수 있습니다. 

문제링크: https://www.acmicpc.net/problem/1783

문제의 규칙입니다.

1. 2칸 위로, 1칸 오른쪽
2. 1칸 위로, 2칸 오른쪽
3. 1칸 아래로, 2칸 오른쪽
4. 2칸 아래로, 1칸 오른쪽

그리고 4회이상 이동시 4가지이동을 포함해야한다는 규칙이 있습니다.

만약 n이 1이라면, m값과 관계없이 이동이 불가하기 때문에 1입니다.

만약 n이 2이라면, 2번과 3번 이동이 가능해집니다.

올라갔다 내려갔다 하면서 이동할 수 있겠죠! 하지만  4회이상 이동시 4가지이동을 포함해야한다는 규칙때문에 3회의 이동까지만 가능합니다. (1번, 4번이동은 2칸 씩 이동해야하지만 그것이 불가능하기 때문에) 

만약 n이 3이상이라면, 규칙적으로 이동하게 됩니다. m이 7이상이여서 문제의 규칙 1, 2, 3, 4번 이동이 모두 가능하다면 각각 4번의 이동를 하고 그 이후부터는 1, 4번 이동만을 반복할 것입니다. (가장 많이 탐색하기 위해서)

즉, m-2번 탐색이 가능해집니다.

위의 3가지 규칙을 생각하면서 예외를 처리해주시면 됩니다.

정답코드입니다.

#include <iostream>
#include <algorithm>
using namespace std;

int n, m;
int main() {
	cin >> n >> m;
	if (n == 1) {
		cout << 1 << endl;
	}
	else if (n == 2) {
		if (m >= 7)
			cout << 4 << endl;
		else
			cout << (m + 1) / 2 << endl;
	}
	else {
		if (m >= 7) {
			cout << m - 2 << endl;
		}
		else {
			cout << min(4, m) << endl;
		}
	}
}

n 의 갯수마다 처리해야할 예외가 다릅니다. 

조건문들의 조건은 직접 그림을 그리며 이해해보세요.

화이팅! :)