재밌는 문제 풀어보셈요(10.20)(2000덕)
게시글 주소: https://orbi.kr/00069551380
간단한 정수 문제이지만
사실 증명이 메인이라 증명도 간략하게 써주시면 감사하겠습니다!
난이도 :2.5/5
0 XDK (+0)
유익한 글을 읽었다면 작성자에게 XDK를 선물하세요.
-
는 무슨 11년동안 3번이지롱~~~
-
추천좀요!
-
마치 우리의 1교시는 천천히 풀어냄과 동시에 빠른 템포를 유지해야 하는 것처럼...
-
나는 공부를 못 해 14
-
천만덕 가쥬아
-
오랫동안 공부해본 적이 없어서 힘들다.... 내가 좀 불안해서 그러는데 혹시 이번...
-
매번 12시전에 취침에 들어가겠다고 다짐하는 나 자신 1
하지만 절대 안지킨다
-
자기 씨앗(?)을 뿌려서 번식하는 하얀색 식물이요 한 번쯤 발로 차본 얘
-
어떤 글을 봤을때 쓰고싶은 이모티콘이 생각나고 그게 어느위치에 있는지까지 기억남...
-
영어 좀 한다거나 1~2등급 받고 싶은 분들은 이 문장 하나만 해석해 보세요 2
안녕하세요~ 일등들의 공부법학교 일공학교입니다^^ 오늘은 영어 좀 한다는 사람도...
-
수능 출제 7
언제 마감된 건가요?!
-
옯창특 3
쓸글이 있어서 오르비에 들어가는게 아니라 오르비에 들어가기 위해 쓸글을 고안해냄
-
2017학년도 나형 21번 같은 쌩으로 경우의 수 구하는 문제가 요즘에도 나오나요??
-
애라이 싯팔 ㅈ됏다
-
가노라 옥주봉아 2
있거라 경천대야
재밌겠군
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이다.
옙옙