네이버 블로그에서 워드프레스로 블로그 이전 작업중입니다.
하나하나 손으로 옮기고 있어서 좀 오래 걸릴 것 같네요.
일단 지금까지 쓰면서 느낀 워드프레스의 장점은 다음과 같습니다.
XE나 그누보드 같은 설치형 게시판은 별로 마음에 안 들었었는데
워드 프레스는 진짜 마음에 드네요.
코드 하이라이팅 및 수식 입력도 쉬워서 앞으로는 알고리즘 관련 포스팅이 더 많아질 것 같습니다.
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
const int MAX = 100020;
struct report {
int s, e;
report() {}
report(int s, int e) : s(s), e(e) {}
bool operator < (const report &t) const {
if(s == t.s) return e < t.e;
return s < t.s;
}
};
int n, m, k, yFull, nFull;
report yes[MAX], no[MAX];
void input(){
scanf("%d%d%d", &n, &k, &m);
int i;
for(i = 0; i<m; i++){
int ts, te, c;
scanf("%d%d%d", &ts, &te, &c);
//닌자가 없다는 보고는 no에, 있다는 보고는 yes에 저장
if(c == 0) no[nFull++] = report(ts, te);
else yes[yFull++] = report(ts, te);
}
}
bool none[MAX];
int cnt, lFind[MAX], rFind[MAX];
void init(){
//보고들을 좌표 순으로 정렬
sort(yes, yes+yFull);
sort(no, no+nFull);
int i, now;
//닌자가 있다는 보고들을 정리. yes 배열을 스택으로 사용한다.
now = 1;
for(i = 1; i<yFull; i++){
/*
(s1, e1) (s2, e2)일 때 s1 <= s2 && e2 <= e1이면
첫 번쨰 보고를 삭제하고 두 번째 보고만 삽입
*/
while(yFull && yes[now-1].e >= yes[i].e)
now--;
yes[now++] = yes[i];
}
yFull = now;
//닌자가 없다는 보고들을 정리
cnt = n;
int j = 1;
for(i = 0; i<nFull; i++){
if(j < no[i].s) j = no[i].s;
for(; j <= no[i].e; j++){
//닌자가 확실히 없는 덤불은 none 배열에 체크
none[j] = 1;
cnt--;
}
}
//루프가 끝나면 cnt는 '닌자가 있을 가능성이 있는 덤불의 수'가 된다.
/*
lFind[i]는 번호가 i 이하인 덤불 중
'닌자가 있을 가능성이 있는 덤불' 중 가장 번호가 큰 덤불의 번호
*/
for(i = 1; i<=n; i++){
if(!none[i]) lFind[i] = i;
else lFind[i] = lFind[i-1];
}
/*
rFind[i]는 번호가 i 이상인 덤불 중
'닌자가 있을 가능성이 있는 덤불' 중 가장 번호가 작은 덤불의 번호
*/
for(i = n; i>=1; i--){
if(!none[i]) rFind[i] = i;
else rFind[i] = rFind[i+1];
}
}
int left[MAX], lFull, right[MAX], rFull;
vector < int > res;
void solve(){
int i;
//'닌자가 숨어있을 가능성이 있는 덤불'이 k개와 일치한다면 k개 전부가 답.
if(cnt == k){
for(i = 1; i<=n; i++)
if(lFind[i] == i)
res.push_back(i);
} else {
int last;
/*
k개보다 많다면, 탐욕 알고리즘을 사용해 '보고를 만족하는 최소의 닌자 수'를 구한다.
닌자들을 놓을 수 있는 가장 오른쪽 칸에 놓아서 채우는 경우, 가장 왼쪽 칸에 놓아서 채우는 경우를 구한다.
조금 생각해보면 오른쪽에서부터 채울 때와 왼쪽에서 채울 때의 닌자 수가 같다는 것을 알 수 있다. (lFull == rFull)
닌자들을 최소로 사용하여 채울 때 i번째 닌자가 있을 수 있는 가장 왼쪽 좌표가 left[i], 가장 오른쪽 좌표가 right[i]이다.
*/
last = 0;
for(i = 0; i<yFull; i++){
if(last < yes[i].s){
left[lFull++] = lFind[yes[i].e];
last = lFind[yes[i].e];
}
}
last = n+1;
for(i = yFull-1; i>=0; i--){
if(last > yes[i].e){
right[rFull++] = rFind[yes[i].s];
last = rFind[yes[i].s];
}
}
//닌자를 최소로 사용했을 때 k명인 경우
if(lFull == k){
for(i = 0; i<lFull; i++){
/*
k명의 닌자 중 존재할 수 있는 가장 왼쪽 좌표와 가장 오른쪽 좌표가 같은 닌자는 위치가 고정되므로 답이 된다.
그렇지 않은 닌자들은 최소 좌표와 최대 좌표 중 다른 칸에 존재할 수 있는 가능성이 있기 때문에 답이 될 수 없다.
*/
if(left[i] == right[rFull-1-i]){
res.push_back(left[i]);
}
}
//닌자를 최소로 사용했을 때 k명보다 작은 경우 (보고를 만족하는 배치가 존재하기 때문에 k보다 클 수는 없다.)
} else {
for(i = 0; i<yFull; i++){
/*
닌자를 발견했다는 보고에 대해, 보고 범위 이내에 '닌자가 숨어 있을 가능성이 있는 덤불'이 하나인 경우만 답이 된다.
그렇지 않은 덤불들은 닌자가 숨어 있을 가능성이 있는 덤불 중
그 덤불의 바로 왼쪽 덤불과 바로 오른쪽 덤불을 대체해서 선택하면
그 덤불을 선택하지 않고도 모든 보고를 만족시킬 수 있다.
이 경우 닌자의 총 인원 수가 증가할수도 있지만, 현재 닌자 수가 k보다 작기 때문에 상관 없다.
*/
if(lFind[lFind[yes[i].e]-1] < yes[i].s)
res.push_back(lFind[yes[i].e]);
}
}
}
//정답을 출력한다.
if(res.empty()) puts("-1");
else {
for(i = 0; i<res.size(); i++)
printf("%d\n", res[i]);
}
}
int main(){
input();
init();
solve();
return 0;
}
APIO 2012 경비병(Guard) 코드 및 주석입니다.
[이 글은 이전에 쓰던 블로그에서 작성된 이후 새 블로그로 이전된 글입니다.]
게임이 완성에 가까워질수록 사소한 디테일에 신경 쓰지 않게 되는 것 같다. 어느 정도 완성하면 ‘이 정도면 배포해도 상관 없지 않을까’ 하는 마음에 자잘한 부분을 완성하지 않고 배포하게 된다.
예를 들면 뮤트 기능이라던지 게임 도움말이라던지 일시정지 기능 등이 그렇다. 게임의 핵심 기능을 다 완성해서 어서 빨리 사람들 반응을 보고 싶어서 이런 부분을 소홀히 하는 것 같다.
하지만 이런 사소한 기능들이 모여서 전체적인 게임의 완성도를 좌우하는 듯. 요즘은 그래서 이런 사소한 부분들에 신경을 쓰려고 노력하고 있다.
이상 뮤트 기능 만들면서 뻘소리였습니다.
[이 글은 이전에 쓰던 블로그에서 작성된 이후 새 블로그로 이전된 글입니다.]
올해 정보올림피아드에서 유일하게 못 풀었었던 수족관 문제에 재도전해서 다시 풀었다. 풀이는 대회 때랑 동일했다. 결국 남들과 약간 풀이가 다르기는 했지만 동일한 풀이였다. (최대부터 선택하는 것과 최소부터 제외하는 것)
다시 짜는 문제긴 했지만 코딩은 꽤 걸렸다. 대회 때처럼 시간 제한 두고 짜는게 아니라 그냥 느긋한 마음으로 짰는데, 실수를 몇 번 했다. 리넘버링을 하느냐 안 하느냐 등의 사소한 부분도 몇 번인가 바뀌었다. 다행히 실수한 부분을 예제랑 손으로 만든 데이터에서 전부 찾아서 AC는 한 번에 받을 수 있었다.
나는 3KB 정도를 짰는데, 학교에서 같이 나왔던 참가자 중에 1KB 이내로 짠 사람이 있는 것으로 알고 있다. 어떤 부분이 다른지 궁금하다.
며칠 전에는 한국 정보올림피아드 개최 며칠 전에 있었던 경기도 대표 소집 교육 때 나왔던 일본 국가대표 선발고사에 나왔던 문제들을 다시 풀었다. 그 때는 세 문제 중에 한 문제 밖에 풀지 못했었는데, 세 문제를 다 풀 수 있었다.
이전에 풀지 못했던 문제를 풀 수 있게 된다는 건 굉장히 기분 좋은 일인 것 같다. 내가 그 때에 비해 성장했다는 확실한 지표를 보여 주기 때문이다. 그 기간동안 헛살았던 건 아니구나 싶으면서 큰 성취감을 느낄 수 있다.
이번 주 토요일에 국제 정보올림피아드에 나가는 한국 대표를 선발하는 선발고사가 있다. 워낙 잘 하는 사람이 많아서 확실하게 된다고 장담은 못 하지만, 떨어지더라도 ‘아쉬움은 있어도 후회는 없도록’ 준비하고 있다.
선발고사 준비한다고 입시 대비하는 방학 중 프로그램 신청도 안 하고 학교에서 지원해주는 일본 공대 캠프 신청도 날짜가 겹쳐서 못 했다. 포기한 게 많은 만큼 얻는 것도 있으면 좋겠다.
+
수족관 문제
oj.uz
여기에서 풀어 보실 수 있습니다.