백준 13458 시험 감독

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

13458번: 시험 감독

난이도가 높지 않은 구현 문제

DP를 적용해서 시간 효율을 개선했다. 

그러나, int의 범위를 신경 쓰지 않아 틀린 제출을 했다..

 

알고리즘 문제 작성시 최대 범위를 빠르게 추정해서 코드를 작성하는 버릇을 기르자.

#define _CRT_SECURE_NO_WARNINGS

#include <cstdio>

#define MAXNUM 1000000

using namespace std;

int n, b, c, remain;
long long result = 0;

int arr[MAXNUM];
int dp[MAXNUM+1] = {0, };

int main(void) {

	int i, tmp, tmp_result;
	scanf("%d", &n);
	for (i = 0; i < n; i++) {
		scanf("%d ", &arr[i]);
	}

	scanf("%d %d", &b, &c);

	for (i = 0; i < n; i++) {
		if (dp[arr[i]] == 0) {
			tmp = arr[i] - b;
			tmp_result = 1;
			if (tmp > 0) {
				remain = tmp % c;
				if (remain == 0) {
					tmp_result += tmp / c;
				}
				else {
					tmp_result += tmp / c + 1;
				}
			}
			dp[arr[i]] = tmp_result;
		}
		result += dp[arr[i]];
	}

	printf("%lld", result);

	return 0;
}