재밌는 문제 풀어보셈요(10.20)(2000덕)
게시글 주소: https://orbi.kr/00069551380
간단한 정수 문제이지만
사실 증명이 메인이라 증명도 간략하게 써주시면 감사하겠습니다!
난이도 :2.5/5
0 XDK (+0)
유익한 글을 읽었다면 작성자에게 XDK를 선물하세요.
-
오답률 1위 가능? ㅈㄴ헷갈리네
-
-
티비 나와서 내일이면 수능이 치뤄지는 날입니다 전국 수험생들 모두 지금껏 열심히...
-
없어지지 않음?
-
더프 어땟음??
-
난이도 어느정도인지 몰라서 조정식쌤 믿어봐 글편 보고 들어가려는데 난이도 어느정도인가요
-
문제 풀다가 갑자기 궁금해졌는데 전자인가요 후자인가요?
-
정신과 약 때문인지 뷸안해서 그런지는 모르겠지만 요즘 잠드는데에만 2시간은 걸리는...
-
오늘은 이거다 전란? 이것도 봐야지 조만간
-
면접 0
제시문 면접 학원으로 프리즘에듀 가보신 분 계실까요
-
[Web발신]...
-
28번 적분퍼즐 30번 급수
-
1.배달을 시킨다. 2.고객님을 위한 서비스 스티커를 획득한다. 3. 볼에다가...
-
현생 인스타 비계팔로워를 제껴버렸는데 똥글싸개를 왜 팔로우하죠?
-
하 콧물 댕빡쳐 0
집중이 안되요 집중이
-
저 ㄹㅇ ㄹㅈㄷ 감풀이인데 구문같은거 거의 모르고 접속사 단어 +- 뉘앙스같은걸로...
-
14 28 30은 진짜 안나올듯 ㅋㅋ
재밌겠군
18?
THANK(땡)
14?
정답!
증명은...?
6⁴ = 1296 < 2077 < 7⁴ = 2401 이므로
6⁴(1296), 5⁴(625), 4⁴(256), 3⁴(81), 2⁴(16), 1⁴(1)
위의 수들의 합으로 2077을 만들어야 함.
1⁴, 2⁴, ..., K⁴들의 합을 이용해 자연수 N을 만들 때
사용된 수들의 최소 개수 : a[N] 이라 하면
a[N] = if(N > i⁴)min(a[N], a[N - i⁴] + 1) (1 ≤ i ≤ K),
a[1⁴] = a[2⁴] = ... = a[K⁴] = 1 로 정의됨.
여기서 N = 2077, K = 6이므로
이를 c++ 코드로 잘 작성해서 돌려보면 a[2077] = 14가 나옴.
역추적까지 해보면
2×5⁴ + 4⁴ + 7×3⁴ + 4×1⁴ = 2077
임을 알 수 있음.
코드풀이는 좀;;
정수로 증명쉽게 되요 ㅋㅋ
풀면서 자꾸 다이나믹 프로그래밍 생각나길래 그만..저도 dp를 모르는게 아닙니다만..허허 수학은 손으로 풀어야된다고욥!
대충 sketch.
2077==13 (mod16)이고, x^4==0or1 (mod16)이므로 n은 최소 13이다.
옙옙