재밌는 문제 풀어보셈요(10.20)(2000덕)
게시글 주소: https://orbi.kr/00069551380
간단한 정수 문제이지만
사실 증명이 메인이라 증명도 간략하게 써주시면 감사하겠습니다!
난이도 :2.5/5
0 XDK (+0)
유익한 글을 읽었다면 작성자에게 XDK를 선물하세요.
-
캬 힘들엇다
-
4번이 너무 맞아서 4번 찍고 맞추긴 했는데요 3번이 맞는거처럼 느껴져요… 아홉...
-
따는 사람은 호감이 있을건데 번따 당하는 사람은 그 사람한테 쌍방이 아니면 무조건 실패아님?
-
젠지진짜뭐함? 1
??
-
쫀떡궁합
-
수능 결과를 바꿀 수 있는 마지막 한달! 동안 해야할 것. 0
수능이 한 달도 채 남지 않았습니다. 다들 수험생이 된 지 얼마 되지 않은 것...
-
. 4
ㅍㅓ엉
-
희망을 다 버렸지만 물어본다…… 이거 어캐고침 ㅜ분명 멀쩡했다고…
-
Adhd인 줄 알았더니 개심각한 조울증이라 함 추가검사비용 22만원에 거의 4시간...
-
사문 실모추천 1
사만다 리트 둘중에 하나 추천해주십쇼
-
진짜아무생각도없음 가끔실모좃되면생각이좀들긴하는데 그거아니면잘봐도딱히생각이없네 내년에또해야해서그런가?
-
틀딱봇치
-
대성에 파는 파이널 시즌하고 정병호쌤 현강 파이널하고 다른건가요?
-
화1) 2
진심으로 화1보다 화2가 훨 쉬운 듯 옛날옛적 중2때 화1 하고 2는 떴는데 중3때...
재밌겠군
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이다.
옙옙