재밌는 문제 풀어보셈요(10.20)(2000덕)
게시글 주소: https://orbi.kr/00069551380
간단한 정수 문제이지만
사실 증명이 메인이라 증명도 간략하게 써주시면 감사하겠습니다!
난이도 :2.5/5
0 XDK (+0)
유익한 글을 읽었다면 작성자에게 XDK를 선물하세요.
-
학교를 안 다녀 봐서 모르겠네 교과로 쓸 때도 영향 받는 건가요?
-
게딱지는 말도 못하고 독서 세지문 다 난이도 쉽지 않은디 컷이 왜 이모양?
-
차영진 0
팔로워부터 풀커리 타려는데 어떤가요?
-
국정원 안가 보면 우리가 생각도 못한 곳에 안가가 많이 있을 겁니다. 0
위치 대부분이 비밀로 관리되고 있긴 한데, 한번 국정원 안가의 존재가 세상에 드러난...
-
노베는아니고 작수때 4초나왔었는데 이번에 시발점 진도뺼때 상담해주시는 분깨서...
-
과학 기술 지문 1
제가 과학 기술 지문 진짜 못하는데요 이유는 풀 때 마다 무조건 지구 끝까지 찾아갈...
-
이러면 독재를 왜 끊은거지 아
-
리그 5위도 챔스 진출 ㄱㅈㅇ!!
-
지금 친해진애들중에 왜 옛날에 내 팔로우 안받아줫나 물오보면 여친이 받지말라햇다...
-
갠적으로 여기보다 잘나오는 데 몇 없을 듯 ㄹㅇ
-
2~3줄로 선지 없애는 국어 발상과 계산 스킵 바로 보여주는 수학 해석만 띡 있는...
-
ㄹㅇㅋㅋ
-
E장면포인트가 더 중요한거죠? 장면플러스는 이미 기출됏던거라 다시 안나오는거아님?
-
지문의 마지막 문장을 보면 경기 침체기에도 완충자본제도로 비롯한 해결 방안이...
-
저 대성 님 메가 메가에서 영어 1명만 들을 예정입니다
-
80분 안재고 푸나
-
화이트데이라고 4
흑화할래 오늘은 블랙데이다
-
헤이 땡삐삐 너는 지금 우정초콜릿줄 여자도 없잖아 정신차려 땡삐삐
-
출근중 2
오늘만 지나면 주말이다
-
광고차단 어플의 사용자 규칙 기능을 딸깍딸깍 잘 건드리면 원하는 요소를 표시되지...
-
에혀 1
그래 서율대 가자
-
상인상반 0
한종철쌤 상인상반표 알려주실 붐 있나요... 그걸로 폰 비번해놨는데 갑자기 기억이 안낭ㅛ
-
프린트당이나 카피플라자에 불법pdf 제본 맡기면 걸릴 확률 높음?? 참고로 원래 책...
-
D-244 4
수학 원순열 오답노트 복습(12문제) 중복순열 오답노트(9문제) 영어단어...
-
얼버기 5
-
창밖에 밤비가 속살거려 육첩방은 남의 나라, 시인이란 슬픈 천명인 줄 알면서도 한...
-
ㅈㄴ 2
아픔
-
아시면 2번 답도 알려주시면 감사하겠습니다
-
???: 메인이 아파요
-
심의와 공론 조사 - 수특 독서 적용편 사회·문화 08 0
안녕하세요, 디시 수갤·빡갤 등지에서 활동하는 무명의 국어 강사입니다. 이번엔...
-
얼버기 1
기상 완료
-
개념때려잡기 2
개념고문하기 개념살인하기
-
.
-
아 늙었나 2
관절에서 소리나는것같음
-
얼버기 1
사실 안잤음
-
모닝공회전 4
으아가ㅏ아가각
-
초등 수학은 다 끝냈고 중등과정 이제 들어감 쎈이나 수학의 바이블같은 교재를...
-
전국서바 5회 0
22번 케이스 찾기가 무슨… 마지막에 22 풀고 다 맞긴 했는데 15초 초과돼서 96점
-
오르비 잘자 3
또 패턴 망했네
-
안녕하세요 저는 검정고시생이고 현역 나이인 오르비언입니다..! 고아름선생님 시대재종...
-
밥 좀 차려줘 2
힘들고 피곤해
-
스피드 좀더 내보자...
-
보통 수학 난이도 20번이 13번보다 어려운건가요? 3
제일 어려운게 14 15 20 21 22 29 30 이렇게 7개임?
-
얼부기 1
-
요리도 더럽게 못하고 생활력도 구지고 개인적으로 나는 그냥 롤을 같이 볼수 있는 사람이면 개꿀일듯
-
외대 폴란드어과 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이다.
옙옙