재밌는 문제 풀어보셈요(10.20)(2000덕)
게시글 주소: https://orbi.kr/00069551380
간단한 정수 문제이지만
사실 증명이 메인이라 증명도 간략하게 써주시면 감사하겠습니다!
난이도 :2.5/5
0 XDK (+0)
유익한 글을 읽었다면 작성자에게 XDK를 선물하세요.
-
젠지따잇각이냐 2
ㅋ
-
미적기준 11~15 쉽 19/20 번호치고 난이도 있는 편 28 어렵...
-
민초 후기 6
아니 이딴걸 왜 먹는거야
-
-
연애가 어려움? 4
걍 머리만 긴 니얼굴 복붙한 여자 사귀면 쉬워~
-
현장응시 97 캬캬
-
을 어떻게 뚫어야할까요 작수 미적 백분위 76에서 6모 9모 둘다 92~4정도인데...
-
.
-
그건 사실 나였고...ㅈㅅ합니다....
-
서바 수학 전국 1
서바 전국 수학 너무 어려운 회차는 빼고 풀려고 하는데 너무 어렵다하는 회차들 좀...
-
왜 국어성적은 그에 비례하지 않는거니.. 게다가 같은 샘인데 ㅠㅠㅠㅠ
-
불안하다 3
불안하다불안하다불안하다
-
시골이라 잇올은없고 ㅠ.. 성인들만 받는 것 같은데 문의 해봐야되나 한번 현역이나...
-
계폭 -> 높은 확률로 수능 gg 다시 돌아와서 n+1을 하는 건 제외..
-
이매진독서핫백 6
Dc squid이거 개어려운데 다들어캐푸셧나요,,,
재밌겠군
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이다.
옙옙