Code Jam to I/O for Women

처음으로 참여해 본 코드잼 39점을 받아 women에서 218등, 한국에선 10등 정도의 등수를 받았다. 심지어 한국에서도 등수가 2자리라니 ㅜㅠ

일단 느낀점은,

1. 방학동안 진자 팽팽 놀기만 했구나
2. 자존심 상한다

ㅋㅋㅋㅋㅋ이런 거에 자존심 상한다니 좀 어이 없을 수 있겠지만, 일단 submit 회수가 너무 많아서 점수가 같은 분들 중 penalty가 거의 제일 많았다. 코딩에나 아이디어 구상에나 잔실수가 너무 많은 것 같다... 구글 가고 싶은데 이대로는 안 될 것 같다. 등수보니까 미친듯이 자존심이 상한다. 딥러닝 스터디 대충 끝나는 대로 바로 boj/leetcode 들어가서 음청 공부해야 겠다. 제발 구글 인턴..! 제발 제발

블로그를 티스토리로 옮길 것 같은데 바로바로 안 쓰면 또 안 할 것 같아서 미리미리 리뷰나 해본다. 나는 Grid Escape과 Parcel Post라는 문제 두개를 풀었다.

Grid Escape

풀이

별로 어려운 문제가 아닌데...ㅠㅜㅜ 무슨 문제인지 이해하는 데 일단 오래걸렸고, 쉬운 방법을 좀 돌아돌아 생각했던 것 같다.

일단 이 문제는 R*C 의 그리드가 있고, 각각의 그리드 칸을 하나의 방으로 생각한다. 하나의 방에는 각각 하나의 단방향 문이 존재한다. 각각의 방에 선수가 있는데 그 중 K명의 선수만 탈출이 가능하게 한 방에 하나씩 문을 놓아주고, 나머지 선수들은 탈출할 수 없도록 문을 놓아주면 된다. 리얼 음청 쉬운 문제였당....

일단 모두 탈출 할 수 있다고 생각하고 모든 방을 N으로 초기화 시켜준다음 차례대로 앞에서부터 K명만 탈출할 수 있게 K+1번째 방의 방향만 S또는 R로 바꿔주면 된다. 글고 위로 탈출하는 거니까 나머지 열 들의 제일 윗 행도 S로 바꿔주면 된다. 이거 문제 못 알아들어서 해매고 탈출못하게 달팽이 설계하고 있다가 시간 날렸다.

죽고싶다.. 쓰레기같은 머리...ㅠㅜㅡ

 

Code

#include <stdio.h>
char arr[103][103];
int main() {
	int T;
	scanf("%d", &T);
	for (int t = 1; t <= T; t++) {
		int K, R, C;
		scanf("%d %d %d", &R, &C, &K);
		if (R*C-K==1)printf("Case #%d: IMPOSSIBLE\n",t);
		else {
			for (int y = 0; y < C; y++) {
				for (int x = R - 1; x >= 0; x--)arr[x][y] = 'N';
			}
			int rx = K % R, ry = K / R;
			if (rx !=R-1) {
				arr[rx][ry] = 'S';
			}
			else if (ry != C - 1) {
				arr[rx][ry] = 'E';
			}
			else
				arr[rx][ry] = 'W';
				
			for (int y = ry + 1; y < C; y++) {
				if (R == 1)arr[0][y] = 'W';
				else arr[0][y] = 'S';
				
			}
			printf("Case #%d: POSSIBLE\n",t);
			for (int i = 0; i < R; i++) {
				for (int j = 0; j < C; j++)printf("%c", arr[i][j]);
				printf("\n");
			}

		}
	}
}

.

Parcel Posts

풀이

이것도 좀.. 왜 이렇게 까지 많이 제출했나 싶다. 진짜 등수보고 깜짝놀래서 어디 높은 데 가서 뛰어내릴 뻔 ㅠㅜ 짲응

음 이문제는 일단 N+1개의 숫자가 주어진다. 그리고 st, mid, en값을 정해서 mid값이 st,en보다 크거나/ mid값이 st, en보다 작으면 parcel이 desirable하다고 인정된다. 이게 뭔소린지는... 항상 구글에서 내는 코드잼이나 킥스타트 같은 문제들은 이해하는 데 더 오랜 시간이 걸리는 것 같다. 뭔가 icpc나 정올 문제들과는 다른 느낌...?

하여튼 N+1(0~N)개의 숫자가 그렇게 있으면 desirable 한 parcel들을 최대한 많이 만들 건데, 여기다가 i번째에 i번째 있는 숫자와 같은 숫자를 추가할 수 있는 것 같다. 그렇게 해서 또 다른 desirable parcel을 만들 수 있다면, 최대한 많이 추가할 수 있는 post의 개수는 몇개인가? 하는 문제다. 근데 이걸 나보고 또 설명하라고 하니 잘 못하겠네... ㅋㅋㅋ

예를 들어 4 8 7 3 5 과 같은 수열이 있다면 2번째에 7을 추가함으로 써 4 8 7 7 3 5 가 된다. 그러면 (4 8 7), (7 3 5)로 두개의 desirable parcel을 만들어낼 수 있다. 그러므로 여기서 추가할 수 있는 최대 post는 1개!

이것도 진짜 뻘짓을 많이 했다... 근데 내가 문제가 좀 헷갈렸던 게 있다. 6 8 9 7 2 1 3 이라는 수열이 있다면 (6 9 7), (2 1 3)으로 이미 두개의 desirable parcel이 만들어지기 때문에 추가할 수 있는 post는 0개 아닌가? 했지만 여기서 7을 추가함으로 써 (2 1 3) 대신 (7 1 3)이 가능하기 때문에 추가하는 방향으로 생각해야 한다. 그래서 답은 1개. 이것 때문에 뻘짓을 많이 했다! 첨부한 Code 에서 주석 처리해놓은 else if때문에 이게 아닌가? 싶어 여러번 제출하다가 페널티 7개 받았다 ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ아씨...

ㅠㅡㅜ 하여튼 이건 그냥 내가 앞의 수 보다 크면 sum++, 작으면 sum-- 해서 parcel와 시작과 끝에 각각 chk++해주었고, sum/2-1 로 답을 내었다. 왜냐면 parcel이 N개라고 치면 최대 N-1개 추가할 수 있으니까!

 

Code

#include <stdio.h>
int arr[1003],bs[1003];
int main() {
	int T;
	scanf("%d", &T);
	for (int t = 1; t <= T; t++)
	{
		int N; scanf("%d", &N);
		for (int i = 0; i <= N; i++) {
			scanf("%d", &arr[i]);
			bs[i] = 0;
		}
		int sum = 0,chk=0,same = 0;
		for (int i = 1; i <= N; i++) {
			if (arr[i] > arr[i - 1]) {
				bs[i] = 1;
			}
			else if (arr[i] < arr[i - 1]) {
				bs[i] = -1;
			}
			else {
				bs[i] = bs[i - 1]; continue;
			}
			if (sum == 0 || bs[i - 1] *bs[i]<0) {
				sum += bs[i]; chk++; same = 0;
			}
			/*else if (sum != 0 && bs[i - 1] * bs[i]>0 && !same) {
				same = 1; chk--;
			}*/
			//printf("%d : %d  %d %d\n", i, sum,chk,bs[i]);
		}
		
		chk = chk / 2 - 1;
		if (chk < 0)chk = 0;
		printf("Case #%d: %d\n", t, chk);
	}
}