재밌는 문제 풀어보셈요(10.20)(2000덕)
게시글 주소: https://orbi.kr/00069551380
간단한 정수 문제이지만
사실 증명이 메인이라 증명도 간략하게 써주시면 감사하겠습니다!
난이도 :2.5/5
0 XDK (+0)
유익한 글을 읽었다면 작성자에게 XDK를 선물하세요.
-
빅나티를 변기에 넣고서 내려 0 0
빅나티를 변기에 넣고서 내려
-
Iq 두글자면 어떡해 해야함 0 0
나는 검사해본 적은 없지만 두글자인거같은데
-
연상 만나고싶다 0 0
130살 정도
-
지구과학 n제 추천해주세요 0 0
재수생이고 작년에 지구 3등급 맞아서 지구때문에 재수중입니다개념기출은 올해 다시...
-
오늘 공부 시작 0 0
-
작년 수학 서바 리부트 0 0
어쩌다가 구했는데요거 풀 만한가요
-
물1: 산만 넘으면 가장 쉬움. 어렸을 때부터 많이 해본 놈들이거나 현정훈 듣는...
-
아니.잇올 2 1
교시 중간에 못나가나요? 예를들어 8교시가 7시~8시30분이면 8시에 나온다거나,, 일요일기준으로요
-
안좋은 아침이에요 4 0
공부하기 싫음
-
심기 건드릴까봐 일부러 맨뒷자리에서 자습하고있었는데 걍 조용히 그만하라하면 몰라...
-
얼버기 3 1
큐어 아르카나 섀도우
-
오늘 공부도 화이팅 8 0
-
지인이 만든거 검토해줬는데 2월초에 냈는데 아직도 답장이 없다고 하네요 8주 지나서...
-
키드밀리는 좀 짜치긴하네.. 0 1
앨범은 좋게 들었다만 그래도 짜치네 자기 하꼬 시절 생각 1도 안하는구만
-
7시에 강의실 드와서 4 1
과제하는중.. 아직 1교시까지 한시간 반 남아서 그런지 혼자밖에 없음
-
내일더프야 0 0
끙
-
얼버기 0 0
-
살려다오 2 0
나스닥 왜 신고가야 .....?
-
의지할곳이있다는게.. 1 1
얼마나큰축복인지..
-
ㅠㅠ 5 1
결국 못일어나고 지금 일났네
-
가천대 정도면 잘 간거임?? 6 0
유튜브 댓글 보니까 가천대 갈거면 재수한다 그러는데 막 애매한 애들의 꿈의학교 그러고
-
안냐떼요 7 1
-
26년도 6모 영어 1 0
21,30,32,34,37,39,40,41~42 손도못댐 24 틀림 73점 근데...
-
오늘은 시험이 2개가 잇서요 1 1
그래서 학교에 안씻고 가고 잇어요
-
얼버기 1 0
예정보다 30분 늦게 일어났음;;
-
28부턴 정시 없어지는거임? 1 0
수능100 사라진다고 보면 되는거임?
-
49일차 (4월 14일 화요일) 05:00~09:00 편의점 16:00~27:00...
-
얼버기 0 0
버스놓침 아
-
그냥 지금 학교가는중 0 0
어차피 잠 안드는거 카페인 좀 들이키고 학교 일찍 간다음에 학교끝나면 집가서 수면제 털어먹고 자야지
-
컵라면 2개 야르 0 0
태어나서 처음으로 컵라면 2개 먹어본듯 야르~~
-
밤샘 3 0
천원의아침 드가자
-
와 한숨도 못잤다 0 0
이제는 밤에는 누워도 잠이 아예 안오네 ㅋㅋ
-
기차지나간당 2 0
부지런행
-
얼버기 3 0
-
2학기 그냥 무휴반 하고 싶다 1 0
학교가 너무 좋음
-
빅나티 얘 왜 랩잘함.. 2 0
이런 애였냐
-
하... 다 듣고 자야징
-
강제 얼버기함 4 1
룸메가 시끄럽게해서 지금 깬사람이 있다? 그게 접니다 ㅆㅂ
-
어캄
-
오늘은 일찍 잔다 3 1
-
-
나는죽어도못함
-
이제 검토를 누구한테 시키지,,
-
수특 자연 고전운문 슥 봣는데 0 1
자연에서 내적갈등이 없네 태도가 걍 뭔가 특징적인게 없어
-
에반데
-
샌디는 신이다 5 0
물려도 살려준다 휴...진짜 죽는줄알았다
-
잘자요 0 0
짜요
-
경희한 vs 단국치 1 0
경희대 한의대 vs 단국대 치대(천안캠) 님들이면 어디 고르시나요 4덮 션티 서울대...
-
유키군 실종사건 0 0
새아빠가 범인 ㄷㄷ
-
4시간 잘 수 있군 0 0
내일 1교시 자야징
재밌겠군
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이다.
옙옙