글 읽기 - 1699번 문제에서 큰 수부터 빼 나가면 안되나요?

jhj98 3년 전 0

그렇게 풀어서 프로그램 실행은 이상이 없는데 답이 틀리네요.

혹시 큰 제곱수부터 빼 나가는 것의 반례가 있나요?

											#include<stdio.h>
int a[317];
int main(){
	int i, n, cnt = 0;
	scanf("%d", &n);
	while (n > 0){
		for (i = 1; (i + 1)*(i + 1) <= n; i++);
		n -= i*i; cnt++;
	}
	printf("%d", cnt);
	return 0;
}
										

yukariko 3년 전 3

http://www.acmicpc.net/board/view/960

43이 반례일겁니다. 큰것부터하면 36 + 4 + 1 + 1 + 1 로 5인데 25 + 9 + 9 로 3이 정답입니다.

jhj98 3년 전 0

헐...

yukariko 3년 전 0

52 = 49 + 1 + 1 + 1 or 36 + 16

생각해보니 은근있네요 ㅋㅋ..

jhj98 3년 전 0

점점 산이 높아지는군요... 혹시 해답에 간접적으로 도움이 되는 페이지를 알려주실 수 있나요?

yukariko 3년 전 0

동전 dp 문제와 비슷한 문제라 관련질문글을 보시면 될것같습니다.

동전문제를 먼저 해결하시고 도전해도 좋을거같구요.

site:acmicpc.net/board/ 동전

위 주소를 주소창에 복붙해보세요.

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

문제

문제

출처

ACM-ICPC

1699번 문제에서 큰 수부터 빼 나가면 안되나요?

jhj98 3년 전 0

yukariko 3년 전 3

jhj98 3년 전 0

yukariko 3년 전 0

jhj98 3년 전 0

yukariko 3년 전 0

Baekjoon Online Judge

채점 현황

문제

출처

ACM-ICPC

Coder's High

서버 상태

도움말