재밌는 문제 풀어보셈요(10.20)(2000덕)
게시글 주소: https://orbi.kr/00069551380
간단한 정수 문제이지만
사실 증명이 메인이라 증명도 간략하게 써주시면 감사하겠습니다!
난이도 :2.5/5
0 XDK (+0)
유익한 글을 읽었다면 작성자에게 XDK를 선물하세요.
-
문제에 대한 해설과 더 많은 무료 고난도 문제는 https://t.me/JerryEthic
-
목 씨발 0
자세 좀 제대로 할 걸
-
최저러라서 수능공부 시작한지 두세달 됐는데 수특 문학은 내신때문에 45퍼정도 했고...
-
이제 뭔재미로 사냐
-
짜파게티 먹말 4
ㅃㄹ
-
남들이 내 통번 부족하다고 무시해도 나는 내 갈길을 간다. 남들이 누구 빽으로...
-
얼버기 1
-
최초취득이 정당했던 재화도 이전의 과정의 부정의하다면 교정의 대상이 될수있다고...
-
5셑은 힘들지않을까..
-
야구 하고 있네 0
아까 중단 되었다고 해서 안보고 있었는데!!
-
사실저는 19
국어황입니다 ㅈㅅ 개소리구여 작년에 국어망해서 재수하는 넘임....수미잡
-
현역이라 모르겠는데 원래 이런거임??
-
-> 많이 출제될수밖에 없는듯 미지수의 개수보다 식의 개수가 적을 때 특정한 답으로...
-
3/5/7더프: 백분위 98(보정) 4/8더프 백분위 90(보정) 6평 9평 둘다...
-
이미지vs이창무 6
심화특강 미적을 들을까 아니면 이미지 미친개념을 들을까고민해서 물어봅니드 어떤게 괜찮을까요
-
굿
-
밥안먹고 공부하면 운동도 안하는데 맨날 저혈당이 옴
-
뭔가 공부할때 0
음악 들으면 효율 좋다 생각했는데 빨리지침 요즘은 그냥 귀마개끼고 공부함
-
젠지가 3대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이다.
옙옙