글 읽기 - 시간초과 원인좀 찾아주세요

soloranker66 4년 전 0

계속 50%넘어감과 동시에 시간초과가 나버리는데

어느 부분에서 문제가 생긴걸까요

#include <stdio.h>

int arr[100001];
int dp[100001];

int f(int st, int fin, int num) {
	int m;
	while (fin - st > 0) {
		m = (st + fin) / 2;
		if (dp[m] < num)
			st = m + 1;
		else
			fin = m;
	}
	return fin;
}
int main() {
	int size;
	while (scanf("%d", &size) != EOF) {

		scanf("%d", &size);

		for (int i = 1; i <= size; i++)
			dp[i] = 0;

		for (int i = 1; i <= size; i++)
			scanf("%d", &arr[i]);

		int p = 1;
		dp[1] = arr[1];

		for (int i = 2; i <= size; i++) {
			if (arr[i] > dp[p]) {
				p++;
				dp[p] = arr[i];
			}
			else {
				dp[f(1, p, arr[i])] = arr[i];
			}
		}
		printf("%d\n", p);
	}
}

soloranker66 4년 전 0

해결했습니다..

while문에서 scanf를 받아놓고 또 받은게 문제였네요

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

시간초과 원인좀 찾아주세요

soloranker66 4년 전 0

soloranker66 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말