KOI 2014 초등부 문제 풀이

한국정보올림피아드(정올) 2014년도 초등부 문제 풀이 포스팅입니다.

문제들은 백준저지에서 참고하고 풀이했습니다.

https://www.acmicpc.net/category/detail/1274

총 4문제가 있습니다.

1번 전자레인지 문제입니다. (백준 10162)

https://www.acmicpc.net/problem/10162

나눗셈 연산과 모듈러 연산을 이용하면 간단하게 해결할 수 있습니다.

 

#include <iostream>

using namespace std;

int main() {
	int t;
	cin >> t;
	if (t % 10 != 0) {
		cout << -1 << endl;
		return 0;
	}
	int m300, m60, m10;
	m300 = m60 = m10 = 0;
	
	m300 = t/300;
	t %= 300;
	m60 = t/60;
	t %= 60;
	m10 = t/10;
	cout << m300 << ' ' << m60 << ' ' << m10 << endl;
	return 0;
}

2번 색종이 문제입니다. (백준 10163)

https://www.acmicpc.net/problem/10163

N값이 작으므로, 2차원 배열로 종이 그리드를 모두 나타내고 시뮬레이션 한 뒤 개수를 세면 됩니다.

 

#include <iostream>

using namespace std;

int map[102][102];
int sz[101];
int n;
int main() {
	cin >> n;
	int sx, sy, dx, dy;
	for (int i=1; i <= n; i++) {
		cin >> sx >> sy >> dx >> dy;
		dx += sx;
		dy += sy;
		for (int x=sx; x < dx; x++) {
			for (int y=sy; y <dy; y++) {
				map[x][y] = i;
			}
		}
	}
	
	for (int i=0; i < 101; i++) {
		for (int j=0; j < 101; j++) {
			if (map[i][j]) {
				sz[ map[i][j] ]++;
			}
		}
	}
	for (int i=1; i <= n; i++) {
		cout << sz[i] << endl;
	}
}

3번 격자상의 경로 문제입니다. (백준 10164)

https://www.acmicpc.net/problem/10164

다이나믹 프로그래밍으로 문제를 해결할 수 있습니다. K값이 하나 뿐이므로, (시작점 -> K까지 경로)와 (K지점 -> 도착점까지 경로)를 나누어서 구해주면 된다. 숫자를 1부터 세므로 이에 따른 오류를 조심해야 한다.

get함수를 쓸 때 dp[x][y]는 시작 지점에서 (x, y)까지 도달 할 수 있는 경로의 개수를 뜻한다.

get2 함수를 쓸 때에는, (limitx, limity)에서 (x, y)로 도달할 수 있는 경로의 개수를 뜻한다.

get함수가 호출되었을 때에는 K지점을 기점으로 왼쪽과 위쪽부분의 부분 사각형에만 값이 들어가 있으며 또한 get2함수에서 (limitx, limity)보다 위쪽이나 왼쪽은 0으로 예외처리가 되어있게 처리되어있다.

 

#include <iostream>

using namespace std;
int dp[16][16];

int n, m, k;

int get(int x, int y) {
	if (x < 0 || y < 0) return 0;
	if (x == 0 && y == 0) return 1;
	if (dp[x][y]) return dp[x][y];
	
	return dp[x][y] = get(x-1, y) + get(x, y-1);
}

int get2(int x, int y, int limitx, int limity) {
	if (x < limitx || y < limity) return 0;
	if (dp[x][y]) return dp[x][y];
	
	return dp[x][y] = get2(x-1, y, limitx, limity) + get2(x, y-1, limitx, limity);
}
int main() {
	cin >> n >> m >> k;
	
	if (!k) {
		cout << get(n-1, m-1) << endl;
	} else {
		int xpos = (k-1) / m;
		int ypos = (k-1) % m;
		get(xpos, ypos);
		cout << get2(n-1, m-1, xpos, ypos) << endl;
	}
}

4번 버스 노선 문제입니다. (백준 10165)

https://www.acmicpc.net/problem/10165

케이스를 잘 나누어야 한다. 일단 노선이 직선일 경우에 대하여 생각을 해 보자. 비교 연산자를 재정의해서 소팅해서, 시작위치는 오름차순으로, 끝 위치는 내림차순으로 정렬한다.    

그러면 소팅을 하고 나서 선형탐색을 앞에서 뒤로 할 때, 뒤에 나타난 녀석이 앞에 있는 녀석을 포함하는 경우는 없다. 

시작위치는 뒤로 갈 수록 앞으로 가기 때문에 시작 범위는 줄어들기 마련이다.    

그리고 시작 위치가 고정인 상태에서는 끝나는 위치는 계속해서 작아지게 되어있으므로, 시작 위치가 다음 값이 되었을 때 끝 위치가 가장 큰놈 일 것이다. 이러한 점을 이용해서 끝놈 위치만 저장해 놓고, 끝놈보다 작으면 포함시켜버리고, 끝놈보다 크면, 그 끝놈 위치를 새 끝놈 위치로 저장해서 끝만 비교하면서 선형 탐색을 하면 된다.    

그러면 또 노선이 원형일 경우를 체크를 해야 하는데, 시작점<끝점 의 경우 A그룹으로 정의하고 시작점>끝점 의 경우를 B그룹으로 정의를 하자. B그룹의 경우는 0번위치를 무조건 통과하고 A그룹은 0번 위치를 지나갈 수는 없다. 따라서 A그룹이 B그룹을 포함할 수는 없다. 

B그룹에서 시작 부분의 최대값을 구하고, 끝 부분의 최소값을 구해서 A그룹의 (?~시작부분 최대값) 의 경우와 (끝부분 최소값~?)을 모두    

포함할 수 있다. 이러한 경우를 체크해 주고(B가 A를 포함하는 경우) A그룹이 A를 포함하는 경우와 B그룹이 B를 포함하는 경우는 직선에서 비교하는 것과 똑같은 방법으로 체크하면 된다.

 

#include <bits/stdc++.h>
using namespace std;

int n, m;

struct Route {
    int src, dst, num;    
};

bool cmp(const struct Route& lhs, const struct Route& rhs) {
    if (lhs.src != rhs.src) return lhs.src < rhs.src;
    return lhs.dst > rhs.dst;
}

vector<Route> small, large; //인덱스 숫자가 작을수록 범위가 큰놈이다.
vector<bool> ans;
int main() {
    cin >> n >> m;
    ans.reserve(m+1);
    int large_over = -1;
    int large_below = n+1;
    int over = 0;
    for (int i=1; i<=m; i++) {
        Route tmp;
        scanf("%d %d", &tmp.src, &tmp.dst);
        tmp.num = i;
        if (tmp.src < tmp.dst) {
            small.push_back(tmp);
        } else {
            large_over = max(large_over, tmp.dst);
            large_below = min(large_below, tmp.src);
            large.push_back(tmp);
        }
    }
    sort(small.begin(), small.end(), cmp);
    sort(large.begin(), large.end(), cmp);
    
    //초기 large_over값은 large가 small 덮어쓰는 경우(0~over 범위로 덮는 경우임)
    //초기 large_below값은 large가 small 덮어쓰는 경우(below~N) 범위로 덮는 경우
    //진행하다보면 small이 small 덮어쓰는 경우도 있음
    for (size_t i=0; i < small.size(); i++) {
        if (small[i].dst <= large_over) ans[small[i].num] = true;
        else if (small[i].src >= large_below) ans[small[i].num] = true;
        if (small[i].dst <= over) {
            ans[small[i].num] = true;
        } else {
            over = small[i].dst;
        }
    }
    over = -1; //large가 large 덮어쓰는 경우
    for (size_t i=0; i < large.size(); i++) {
        if (large[i].dst <= over) ans[large[i].num] = true;
        else over = large[i].dst;
    }
    
    for (int i=1; i <= m; i++) {
        if (!ans[i]) {
            cout << i << '\n';
        }
    }
    
	return 0;
}