재밌는 문제 풀어보셈요(10.20)(2000덕)
게시글 주소: https://orbi.kr/00069551380
간단한 정수 문제이지만
사실 증명이 메인이라 증명도 간략하게 써주시면 감사하겠습니다!
난이도 :2.5/5
0 XDK (+0)
유익한 글을 읽었다면 작성자에게 XDK를 선물하세요.
-
과잠빨리두ㅛㅔ요 1
흐히
-
남쪽은 따뜻하네용 ㅇㅅㅇ
-
심장이자지말래 3
인데놀on
-
-
밴드 말고 스쿨아이돌 동아리 같은거 하고싶은데
-
아 코막히니까 미치겠네요
-
바막 쳐돌이라 바막 하나 사려고 하는데 30임 흠 에어팟 하나값인데 어카지 살? 밀?
-
5등급 정도 되는 실력이고 그동안 쎈같은 유형서만 풀다가 얼마전에 기출 들어갔습니다...
-
병신같아 0
황당하노
-
뉴런은 고정으로 들을건데 개념원리 독학하면서 쎈b 푸는건 좀 그른가요..? 개념원리...
-
-
상용로그 2
수능에 나와요? 안래도되나요?? 저번에 학원에서는 빼고 하라 하긴 했는데 이제 학원...
-
외계 행성 탐지 - 수특 독서 적용편 과학·기술 04 0
안녕하세요, 디시 수갤·빡갤 등지에서 활동하는 무명의 국어 강사입니다. 오늘은...
-
당떨어진다 0
포도당캔디 두개 털어넣었는데도 힘듦 징거더블다운 처방이 필요해보임
-
술을 부워라 비워라 지금 잠
-
운동해야되나 ㄹㅇ
-
난 소리에 집중돼서 잠 더 안 오던데
-
건기식 다이소에 팔아서 약사들이 화났다 이렇게 여론 형성되는거 보고 선동이 무섭긴...
-
손~~
-
진짜잠바이 1
두바이
-
이 분의 조언을 얻고 시도해봤습니다 감사합니다 형님
-
남은 세 분 6
자고 일어나서 쓰겠습니다
-
태도 교정에 이만한 n제 없는 것 같습니다 복습에 정말 좋은 n제 같아요..!
-
2~3등급 진동 중인데 배송오는거 지금 시기에 푸는게 낫나요 나중에 푸는게 낫나요...
-
사탐런 1
안정 2 받기에 가장 변수 적은 사탐 과목이 뭔가요..? 물리 지구 했었고 지구는...
-
심심한데요 12
질문 좀 받고 싶어서 한번씩만 해주세요 너무 개인적인거만 아니었으면 좋게써요
-
자다깸 4
인생망함
-
왤케 다들 어리지
-
정체성 자체가 사라지는 느낌이라 못 바꾸겠음
-
레전드 댕청상태임
-
신청받았던 프사그림 32
https://orbi.kr/00072402792 신청하신분들 각각 잘라서 댓으로...
-
존나 이쁨 백예린닮음 그래서 못잊믄거옇음..
-
자다가 깨서 0
망해버림
-
D-248 2
수학 원순열 문제풀이(9문제) 중복순열 유형7(39문제) 오늘은 정답률이 높았다....
-
이거 이상성욕임? 18
내 가능충 마지노선인데 솔직히 이정도는 정상 범주 아닌가 이거랑 주토피아 주디
-
자러감 6
바이바이
-
4차함수 들고 왔었는데 존꼴이라고
-
몰루레후 어떻게든 되겠지
-
하 이게 차단당할일이야?
-
설치는 414.2 맞나
-
진짜 트럼프는 전설이다..
-
-
오르비 디톡스
-
ㅇㅈ 13
-
아 잠안와 4
놀아줘
-
하던대로 하자 3
새벽을 써서 공부,학교에서 공부 불가 -> 취침
-
흠
-
또선생vs션티 0
둘 다 들어보신분들 얘기 좀 해주세요ㅠㅠ 션티의 abps를 또선생님 수업할때 적용해도될라나
-
에타 너무 질려
-
이정도면 공대 ㅇㄷ감? 19
81 97 1 100 85 백분위기준
재밌겠군
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이다.
옙옙