Codeforces Round #614 (Div. 2) - A. ConneR and the A.R.C. Markland-N

http://codeforces.com/contest/1293/problem/A

Problem - A - Codeforces

 해당 문제는 Markland-N이라는 업체에서 공사를 진행 중인데 conner 가 식당을 갈 때 최소한으로 계단을 이동하는 수를 구하는 문제이다. 첫 번째 입력 t는 전체 testcase 수, N 은 현재 건물에 총 높이 S는 현재 CONNER의 위치 K는 문이 닫힌 식상의 층수의 수이다. 다음으로는 K 개의 닫힌 식당의 층수가 입력으로 들어온다.

 

문제의 제약사항으로 K 의 수는 MIN(N-1, 1000) 층수는 1000개 이하이며 K의 닫힌 식당의 층 수는 1보다 크거나 N 보다 작다.

 

단순하게 생각해서 S(Conner)의 현재 위치에서 닫히지 않는 층 수중 가장 최솟값을 출력하는 식으로 brute-force로 접근하였다.

#include <iostream>
#include <sstream>
#include <string>
#include <algorithm>
#include <functional>
#include <vector>
#include <list>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <stack>
#include <math.h>
#include <memory.h>
using namespace std;
 
#define MAX_SIZE 100
#define INF 0x7fffffff
#define CENDL "\n"
#define ll long long
 
#define c_reverse(s) reverse(s.begin(), s.end())
#define c_sort(s) sort(s.begin(), s.end())
#define print_vector(v) for(int i=0; i<v.size(); i++) cout << v[i];
 
int main() {
 
    cin.tie(0);
    std::ios::sync_with_stdio(false);
 
    int t; cin >> t;
 
    while (t--) {
        long long n, s, k; cin >> n >> s >> k;
        
        vector<long long> arr(k);
        map<long long, long long> mm;
        for (int i = 0; i < k; i++) {
            cin >> arr[i];
            mm[arr[i]];
        }
 
        sort(arr.begin(), arr.end());
        long long sol = 9876543210;
        long long minValue = min(arr[0], (long long)1);
        for (long long i = minValue; i <= max(n, arr[k-1]); i++) {
            
            if (mm.count(i))
                continue;
            long long cand = abs(i - s);
            sol = min(sol, cand);
        }
        cout << sol << CENDL;
    }
    return 0;
}

 

상기 코드처럼 map 에다가 닫힌 K의 층을 담아 두고 가장 낮은 층부터 비교하는 식으로 처음에 구현하였지만 아래 코드에서 시간 초과가 발생한다. 주화 입마 상태에 빠져서 무엇이 문제인지 못 찾았다.

 

병맛 생각에 주화임마에 빠진 코드

sort(arr.begin(), arr.end());
// 오름 차순으로 정렬하고 최소 값부터 비교하기 위해 
long long sol = 9876543210;


long long minValue = min(arr[0], (long long)1);
// 최소값부터 시작 하려고 했는데 주화입마상태로 1 부터 설정함

// 반복문에서 n 과 arr[n-1] max 값을 비교 결국 전체 탐색이 되었다.
for (long long i = minValue; i <= max(n, arr[k-1]); i++) {
	
	if (mm.count(i))
		continue;
	long long cand = abs(i - s);
	sol = min(sol, cand);
}

 

문제에서 주어주는 제약 사항중 N의 값은 2 ≤ N ≤ 10^9 제약을 주었고 또한 K의 수는 MIN(N-1, 1000) 1000보다 작게 주어진다고 보장하였으나. 현재 작성한 코드는 만약 N의 값이 10^9 이면 1부터 10^9 승까지 찾게 되는 코드가 되었다. ㅠㅠㅠ

 

 

전체 층 10 CONNER의 위치 2 닫힌 식당의 수 6

닫힌 층 1 2 3 4 5 7

층수	판정	CONNER 와의 거리
1	X	1
2	X	0
3	X	1
4	X	2
5	X	3
6	O	4
7	X	5
8	O	6
9	O	7
10	O	8

 

CONNER의 현재 위치에서 -1, +1, 현재 위치 더해가면서 가장 적은 거리를 찾는 방법으로 다시 생각 보았다. 그리고 현재 위치에서 이동하면서 최초에 찾으면 더 이상 위아래로 이동하면서 위치를 찾을 필요가 없었다. CONNER의 현재 위치에서 가장 최소한이 이동 거리를 찾는 문제 이기 때문에...

 

#include <iostream>
#include <stack>
#include <string>
#include <vector>
#include <map>
#include <algorithm>
using namespace std;
 
int main() {
 
	int t; cin >> t;
	while (t--) {
		int n, s, k;
		cin >> n >> s >> k;
		vector<int> arr(k);
		map<int, int> mm;
		for (int i = 0; i < k; i++) {
			cin >> arr[i];
			mm[arr[i]];
		}
 
		for (int i = 0; i < 1001; i++) {
 
			int up = s + i;
			if (mm.count(up) == false && up <= n) {
				cout << i << "\n";
				break;
			}
 
			int down = s - i;
			if (mm.count(down) == false && down > 0) {
				cout << i << "\n";
				break;
			}
		}
	}
	return 0;
}

 

후기

"난 바보다. 어떻게 이런 실수를" 

 

반성 : 왜 이런 간단한 것을 해결 못했을까? 원인을 적으세요.
1. 범위를 제대로 인식 못함
2. brute force 접근을 너무 무리하게 함.

-> 10억층까지 전부 확인하고 가장 가까운 것을 찾으려고 했음

또다시 실수를 하지 않기 위해
1. 범위부터 확인하고 알고리즘을 구현해야 함.
2. 무조건 범위관련된건 전부 종이에 적어놓고 시작하자.

 

이런 걸 알려주는 최성준 님에게 감사의 마음을 가지자
아무나 안 알려준다능