카테고리: BOJ

루프 순서에 유의하자.

 

#include <stdio.h>

#define N_SIZE		(100)
#define N_OFFSET	(2)
#define N_MAX		(N_SIZE + N_OFFSET)

int main() {
	int n, m, src, dest;
	int graph[N_MAX][N_MAX];
	int minIndex = 1;
	bool loop = true;

	scanf("%d %d", &n, &m);

	for (int i = 0; i < m; i++) {
		scanf("%d %d", &src, &dest);
		graph[src][dest] = graph[dest][src] = 1;
	}


	for (int k = 1; k <= n; k++) {
		for (int i = 1; i < n; i++) {
			for (int j = i + 1; j <= n; j++) {
				if (graph[i][k] && graph[k][j]) {
					if (graph[i][j] == 0 || graph[i][k] + graph[k][j] < graph[i][j])
						graph[i][j] = graph[j][i] = graph[i][k] + graph[k][j];
				}
			}
		}
	}

	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			graph[i][0] += graph[i][j];
		}

		if (graph[i][0] < graph[minIndex][0]) {
			minIndex = i;
		}
	}

	printf("%d\n", minIndex);

	return 0;
}

 

• 풀이법 : 플로이드-워셜 알고리즘
• 주의 : 플로이드-워셜 알고리즘은 k, i, j 순으로 루프를 타야되는걸 주의

신선하고 재밌는 문제

 

int –2147483648

 

• 풀이법 : Overflow
• 참고 : Integer range –2,147,483,648 ~ 2,147,483,647

#include <stdio.h>


int main() {
	int T;
	
	scanf("%d", &T);
	
	while (T--) {
		char str[10010] = { 0 };
		long long result = 1;
		int before = 0, cnt = 0;

		scanf("%s", str);

		for (int i = 0; str[i]; i++) {
			if (str[i] != '?') {
				if(before){
					if (before != str[i]) {
						result *= (cnt + 1);
						result %= 1000000007;
					}
				}
				before = str[i];
				cnt = 0;
			}
			else {
				cnt++;
			}
		}

		printf("%lld\n", result);
	}

	return 0;
}

 

날로먹는 문제

 

#include <stdio.h>

int main() {
	int n, l, pos, cnt = 0;
	bool pipe[1001] = { 0 };

	scanf("%d %d", &n, &l);

	for (int i = 0; i < n; i++) {
		scanf("%d", &pos);
		pipe[pos] = true;
	}

	for (int i = 0; i <= 1000; i++) {
		if (pipe[i]) {
			for (int j = 0; j < l && i + j <= 1000; j++) {
				pipe[i + j] = false;
			}

			cnt++;
		}
	}

	printf("%d\n", cnt);

	return 0;
}

 

그냥 간단한 DP문제.
m이 먼저나왔으면 좋았을텐데, 동전을 다 받은다음 나온다.
dp 테이블 크기가 작고 귀찮아서 대충 풀었는데, 시간복잡도를 고려하면 배열을 선언해서 동전을 저장한 다음, m을 받고 난 뒤, dp테이블을 m까지 계산하는게 빠르다.

 

#include <stdio.h>

int main() {
	int T;

	scanf("%d", &T);

	while (T--) {
		int dp[10010] = { 1 };
		int n, c, m;

		scanf("%d", &n);

		for (int i = 0; i < n; i++) {
			scanf("%d", &c);

			for (int i = 0; i <= 10000 - c; i++) {
				if (dp[i]) {
					dp[i + c] += dp[i];
				}
			}
		}

		scanf("%d", &m);

		printf("%d\n", dp[m]);
	}

	return 0;
}

 

풀긴 풀었는데, 솔직히 테스트케이스가 부실해서 통과한거 같다.
대회에서 사용했던 I/O(http://acmacpc.org/archive/y2013/)로 테스트해보면 간당간당한게 몇 개 있다. 내 컴퓨터에서 약 2~3초 정도 걸리는데, BOJ서버에선 3초를 넘길 거 같다.

 

풀어도 찜찜한 이 기분. 그래서 정석 풀이법을 찾아봤다.
대회에 참가했던 사람에 의하면 이 문제의 출제 의도는 Meet in the middle로 푸는것이라 한다.(https://www.quora.com/This-algorithmic-problem-wasnt-solved-on-a-recent-ACM-ICPC-regional-contest-How-can-it-be-solved/answer/Islam-Diaa)

 

나의 경우엔 백트래킹으로 풀었다.
계속 타임리밋이 뜨길래 메모이제이션에 inline까지 써가면서 처절하게 풀었는데 효과가 없었다. 디버깅을 해보니 함수콜에 오버헤드가 큰 것이 원인이였다.
(inline인데 왜 오버헤드가 큰걸까… 예전에 C++배울땐 매크로함수랑 똑같은 기능이라 배운것 같은데…)

 

그래서 최대한 함수콜을 줄이기 위해 내림차순으로 정렬한 뒤 백트래킹을 진행했다.
이렇게하면 if (dmg + remain_dmg < hp) return;과 연계되어 함수콜이 많이 줄어든다.

나름 많이 헤맨거 같은데 모로가도 서울만 가면 된다고, 메모리 & 시간으로 1등먹어서 기분 좋다.

 

#include <stdio.h>

long long stat[5][3] = { 0 };
long long memo[1002][5][2] = { 0 };
long long T, hp;
long long  minCost, minDmg;


long long pow(long long val, int k) {
	long long result = 1;

	for (int i = 0; i < k; i++) {
		result *= val;
	}

	return result;
}
inline void backtracking(int charCode, long long dmg, long long cost, long long remain_dmg) {
	long long _cost, _dmg;

	if (dmg + remain_dmg < hp)
		return;

	for (int i = 0; i <= stat[charCode][0]; i++) {
		_cost = cost + memo[i][charCode][1];
		_dmg = dmg + memo[i][charCode][0];

		if (_cost > minCost)
			return;
		
		if (_dmg >= hp) {
			if (minCost >= _cost) {
				if (minCost != _cost || minDmg >= _dmg)
					minDmg = _dmg;

				minCost = _cost;
			}

			return;
		}

		if (charCode < 4) {
			backtracking(charCode + 1, _dmg, _cost, remain_dmg - memo[stat[charCode][0]][charCode][0]);
		}
	}
}

int main() {
	scanf("%lld", &T);

	while (T--) {
		long long maxDmg = 0, maxCost = 0;
		
		minCost = pow(10, 12) * 5;
		minDmg = pow(10, 12) * 5;
		
		scanf("%lld", &hp);

		for (int i = 0; i < 5; i++) {
			scanf("%lld %lld %lld", &stat[i][0], &stat[i][1], &stat[i][2]);
			maxDmg += stat[i][0] * stat[i][1];
			maxCost += stat[i][0] * stat[i][2];
		}

		if (maxDmg <= hp) {
			if (maxDmg == hp) {
				printf("%lld %lld\n", maxCost, maxDmg);
			}
			else {
				printf("We are doomed!!\n");
			}
		}
		else {
			for (int i = 0; i < 4; i++) {
				for (int j = i + 1; j < 5; j++) {
					if (stat[i][0]  < stat[j][0]) {
						stat[i][0] ^= stat[j][0] ^= stat[i][0] ^= stat[j][0];
						stat[i][1] ^= stat[j][1] ^= stat[i][1] ^= stat[j][1];
						stat[i][2] ^= stat[j][2] ^= stat[i][2] ^= stat[j][2];
					}
				}
			}

			for (int i = 0; i < 5; i++) {
				for (int j = 0; j <= stat[i][0]; j++) {
					memo[j][i][0] = stat[i][1] * j;
					memo[j][i][1] = stat[i][2] * j;
				}
			}
			backtracking(0, 0, 0, maxDmg);
			printf("%lld %lld\n", minCost, minDmg);
		}
	}

}

 

이건 솔직히 영어 지문 해석 문제다.

 

#include <stdio.h>

int main() {
	int T;
	int n;

	scanf("%d", &T);

	while (T--) {
		int timeline[1010] = { 0 };
		int a, b, max = 0;

		scanf("%d", &n);

		for (int i = 0; i < n; i++) {
			scanf("\n%*c %d %d", &a, &b);
			max = max > b ? max : b;

			for (; a < b; a++)
				timeline[a]++;
		}

		for (int i = 0; i < max; i++) 
			timeline[i] > 0 ? printf("%c", 'A' + timeline[i] - 1) : NULL;
	
		printf("\n");
	}

	return 0;
}