재밌는 문제 풀어보셈요(10.20)(2000덕)
게시글 주소: https://orbi.kr/00069551380
간단한 정수 문제이지만
사실 증명이 메인이라 증명도 간략하게 써주시면 감사하겠습니다!
난이도 :2.5/5
0 XDK (+0)
유익한 글을 읽었다면 작성자에게 XDK를 선물하세요.
-
얼버기 0 0
예정보다 30분 늦게 일어났음;;
-
28부턴 정시 없어지는거임? 0 0
수능100 사라진다고 보면 되는거임?
-
49일차 (4월 14일 화요일) 05:00~09:00 편의점 16:00~27:00...
-
얼버기 0 0
버스놓침 아
-
그냥 지금 학교가는중 0 0
어차피 잠 안드는거 카페인 좀 들이키고 학교 일찍 간다음에 학교끝나면 집가서 수면제 털어먹고 자야지
-
컵라면 2개 야르 0 0
태어나서 처음으로 컵라면 2개 먹어본듯 야르~~
-
밤샘 1 0
천원의아침 드가자
-
와 한숨도 못잤다 0 0
이제는 밤에는 누워도 잠이 아예 안오네 ㅋㅋ
-
기차지나간당 2 0
부지런행
-
얼버기 2 0
-
2학기 그냥 무휴반 하고 싶다 1 0
학교가 너무 좋음
-
빅나티 얘 왜 랩잘함.. 1 0
이런 애였냐
-
하... 다 듣고 자야징
-
강제 얼버기함 4 1
룸메가 시끄럽게해서 지금 깬사람이 있다? 그게 접니다 ㅆㅂ
-
어캄
-
오늘은 일찍 잔다 2 1
-
-
나는죽어도못함
-
이제 검토를 누구한테 시키지,,
-
수특 자연 고전운문 슥 봣는데 0 1
자연에서 내적갈등이 없네 태도가 걍 뭔가 특징적인게 없어
-
에반데
-
샌디는 신이다 4 0
물려도 살려준다 휴...진짜 죽는줄알았다
-
잘자요 0 0
짜요
-
경희한 vs 단국치 0 0
경희대 한의대 vs 단국대 치대(천안캠) 님들이면 어디 고르시나요 4덮 션티 서울대...
-
유키군 실종사건 0 0
새아빠가 범인 ㄷㄷ
-
4시간 잘 수 있군 0 0
내일 1교시 자야징
-
언미생지 인공호흡기좀.. 0 0
지금 숨이 안 쉬어짐
-
빅나티 맞디스나왔네 0 0
근데 들어보니까 하남자들 싸움인거깉네
-
6시간전에 먹긴함
-
아배고파 4 0
한끼만머거
-
누워요 2 3
가볍게 숨을 뱉어요
-
동력이 없는게 무서운 이유 0 1
동력차가 없이 발전차만 조성된 편성은 아무런 추진력을 갖지 못하고 역 구내 또는...
-
헐드엄세이에 0 1
마룬파이브가 피처링한 라이브버전이 있네
-
혹시 휘양찰랑 7 0
이라는 유행어.. 같은 게 있나? 안 그러면 살짝 충격적인 맞춤법인데
-
슬퍼
-
저랑 X스 하실분? 5 0
연락 주세요.https://www.chess.com/member/Orbi-Tree08
-
오늘 새르비는 여기까지 2 1
-
슬슬 잠이 온다 4 0
어제 밤을 샜으니 뭐..
-
확실히 교수님들은 3 2
본인이 가르치시는 분야의 씹덕들을 좋아하심
-
게임프사도 과학임 0 1
ㄹㅇ
-
대통령 공약이행률과 좋은 승부 가능함
-
진짜 이짓까지는 안할려햇는데 4 2
작수 끝나고 오랜만에 밤새는데 지금 좀비고 한판 돌릴까 어차피 4시간 뒤에 배드민턴 가야하는데
-
수능 국어 처음 공부할 때 0 0
예비 매삼비, 예비 매삼문-> 매삼비, 매삼문-> 윤혜정 개념의 나비효과->수국김...
-
졸려 4 1
근데 자고 싶지가 않아
-
배고프다 0 0
저녁을 너무 조금먹었어
-
벡터라는건 2 2
인공지능에서 대단히 핵심적인 요소라는 사실
-
어찌됐든 0 1
이수교과만 보면 난 물1 화1 지1 물2 화2 미적 확통 기하를 다한 인재란말이지
-
백100은 운의영역이고 3 2
솔직히 전과목백98~99 맞을자신있음
-
애니프사는 솔직히 과학이다 7 2
야식 추천좀
-
무정 2 0
재밌겠군
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이다.
옙옙