재밌는 문제 풀어보셈요(10.20)(2000덕)
간단한 정수 문제이지만
사실 증명이 메인이라 증명도 간략하게 써주시면 감사하겠습니다!
난이도 :2.5/5
0 XDK (+0)
유익한 글을 읽었다면 작성자에게 XDK를 선물하세요.
-
보추가 되고싶은 밤이다 21
하와와 오토코노코가 되고싶지만 고기 3인분 구워먹고 살 디룩디룩 찔 예정
-
-
-
여친이 너무 앵김뇨 14
앵드레 킴임뇨
-
오늘 일어나서 지금까지 하루종일 했는데 에2 유지임 시발ㄹㄹㄹㄹㄹㄹㄹㄹㄹㄹㄹㄹㄹㄹㄹ
-
진학사 2
평백 91인데 (수학을 잘봄) 진학사에서 환산점수했을 때 평백 93 94인...
-
언미생지기준 백분위 97 100 2 95 100
-
피의공부머신출발 3
ㄱㄱㄱㄱㄱㄱㄱㄱㄱ
-
큐브에 더 이상 유명한 아이돌 없고 비투비 아이들 다 재계약 안하니까 프미나가 만약...
-
오늘은 올릴게 없다...
-
열심히 만들었는데 댓글이 없어서 울었어...
-
그래서 칭구를 모사귐뇨
-
연대논술 (연세대논술) 2차시험 크게 이변이 생기지 않는이유 0
https://m.blog.naver.com/kcmjungmin36/223677192773
-
-
서울대 의대 교수들이 보여준 모습이 워낙 실망스러웠던 반면에 세브란스 교수님들의...
-
여기서라도 친구 만들고 싶은데
-
맨날 확통 50점받던 애가 수능 확통 다 맞고 70점된거 보고 좀 억울해짐 3
얼마나 쉬운거임 대체..ㅎㅎ
-
말출 1주일전 6
짬평가좀
-
찬우야이! 6
눈이 오면, 임철우.
-
올 수 확통에서 4점 틀리는 거보다 미적에서 12점 틀리는 게 훨씬 잘한 거 같은데 ㅋㅋ
-
미적 1컷 92 국어 언매 1컷 95 국어 화작 1컷 97 1등급 애들이 틀릴...
-
4cm됨뇨
-
n티켓 난이도 3
n티켓 난이도가 어느 정도죠. 쉬4 ~ 준킬?
-
홍대 가능? 2
제방
-
………성적은 반짝거리면서 텔그 아래에서 (문과를 말하는 성적) 간간히 문과를...
-
얼부기 18
-
생명 3컷 1
3컷이 36이 될 확률 ... 아예 물 건너 갔나요 ㅠㅠㅠㅠㅠ ??
-
여기서 15%씩은 전부 떨어진다고 보는게 마음 편한가요?
-
아니 화장하는 것 자체는 알겠는데 왜 화장하고 이마대고 엎드려서 자요? 화장...
-
해당 기업에 최소 몇년 근무해야함?
-
원점수 기준 어떤게 더 낫나요? 연고대 지망 중이고 서울대까지 도전하고싶습니다.
-
모아나 보러갈가 5
흠
-
한완수 한완기 0
뉴런 수분감했으면 한완수 한완기 안하고 바로 이해원n제 풀어도됨?
-
세계사 0
동아시아사는 해보고 매우 만족스러웠는데 세계사도 비슷한가여?? 특성이나 장단점 알려주세요
-
-
서울대 자연대 , 상경계열 전공 육군 후방에서 복무중 질문 자유롭게 ㄱㄱ
-
갔다오고 나서 너무 피곤해가지고 아 다신 안 갈거야!! 했는데 막상 내년에 가고...
-
뭐야 수퍼소닉으로 오랜만에 컴백해서 반응 좋았고 삐끼삐끼나 뭐 그런 걸로 뜨기도...
-
재수안하고 버틸수있으려나이거
-
레전드기만 8
-
아 3
인생 빨리 머리털 깎든가 해야지
-
이별안하는법 3
이건 드립치면 죽을듯
-
그나마 남초팬덤이던게 아이즈원 프미나였는데
-
주류집단인 솔로에게 저항하는거아님뇨? 반박안받음뇨
-
한번 쯤은 다시 생각해보라고 할 듯...
-
차피 스카이 공대쯤 갈 실력되면 대기업은 무난하게 갈 수 있는거 아닌가요?
-
올 수능 기준 언매 100 가까이 떠야 됨?
-
연고서성한 라인에서 신설이 아닌 학과는 작년컷으로 보정들어가서 개짠데 신설학과는...
-
공부해야되뇨 8
하기시름뇨..
-
행복하세요,,, 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이다.
옙옙