재밌는 문제 풀어보셈요(10.20)(2000덕)
게시글 주소: https://io.orbi.kr/00069551380
간단한 정수 문제이지만
사실 증명이 메인이라 증명도 간략하게 써주시면 감사하겠습니다!
난이도 :2.5/5
0 XDK (+0)
유익한 글을 읽었다면 작성자에게 XDK를 선물하세요.
-
연대 1등 ㅇㅈ 5
그건 모의지원 3명 있는 심리학과였구여~
-
아니 나도 ㅇㅈ 0
보고싶은데
-
보내줘
-
맥주 혼술 하는중이라 못봤네
-
더 이상 쓸 글이 없음 그냥 제가 썼던 글들 정독하셈
-
집합으로 해서 정수점 개수세기를 시키는구나
-
ㅇㅈ메타돌때마다느끼는것 14
나보다못생긴사람은존재하지않는구나
-
가형 시절 틀딱인데 11
요즘 수능 난이도 어떤가요? 가형 100이었는데 요즘 수능 100 맞으려면 얼마나 공부하면 될까요
-
오늘은 진짜 없네 머지
-
ㅇㅈ 6
시작은 재탕으로
-
나 06년생 (전) 현역. 1년동안 국어 공부라고는.. 언매는, 언매 개념? 기출...
-
덕코 받아요 0
그냥 받아요.
-
ㅇㅈ 1
(대충 안중에도 없다 짤)
-
님들 의외로 삼도극 근사가 엄청 옛날부터 있었던 스킬인 거 앎? 5
이거 한완수 초판 (13수능 대비)인데 이때도 활꼴 계산 안 하고 날려버렸음 ㅋㅋㅋㅋㅋ
-
누가 탈릅 했다 6
누구냐
-
공대 물리 2
물리 미리 공부하려고 하는데 수능 물리에서 어느정도 깊이?로 공부해야하나요
-
그것만큼 손쉽게 오르비 굴릴 만한 게 없음
-
밸런스겜 7
1. 모든 과목에서 처음 찍는 한문제 무조건 정답 2. 모든 과목 시간 +5분
-
엄청 잘하는 느낌은 아니였는데 30후반은 넘어보이던데 의대준비하시는거임?
-
수잘싶 11
ㄹㅇ
-
수1 시발점 완강하고 수2 시발점 들어갈려고 했는데, 수1 시발점 하면서 조금...
-
오르비를 굴려야 한다는 의무감에
-
2209 공통 56.98 미적 14.80 총점 71.78 2511 공통 57.75...
-
이때 오르비 안 하고 공부했으면 지금 좀 편하게 공부하겠지..? 라고 생각할 때...
-
고2 모고 321** 입니다 탐구는 생지하려고 합니다(저희 동네 지거국이...
-
분명 집에 1편 2편 CD가 있었는데 부모님이 버리셨는지 찾아도 안 나오는
-
메가스터디 환급 6
성적 다 작성하고 대학 입학했을 때 알아서 환급되는건가요 아니면 제가 따로 뭘 해야지 환급되나요?
-
내일 도로주행 시험이니깐
-
근데 먹을게 없네... 뭐 먹지...
-
리젠 없네 7
장작거리들을 좀 던져줘야 하려나 전통놀이 ON??
-
요즘 오르비 뭔가 12
보이는 사람만 보이고 점점 고여가는 느낌... 10일 쿨타임을 줄이고 문호를 좀 개방해야...
-
맞춰보세뇨관
-
신기한 눈사람있어서 찍었음
-
역시 실생활 적용 GOAT 대 "지구과학1"
-
졸리기 때문입니다.
-
이제 그냥 체념함 될대로 되라 이제 귀찮다
-
실시간 좆됐음 4
어그로 ㅈㅅ 원래 눈 많이 올 때 하늘 밝아짐? 방금 밖에 보고 아침7시인줄 알고...
-
-
입냄새나는고 6
갑자기 입냄새 심해진거 병일수도 있음..? 아빠 치과의사라 ㄹㅇ 양치잘하시고...
-
큐브 깔았어요 2
안녕 큐브
-
어감이 너무 야한데
-
강대 기숙 0
강대기숙 들어갈 것 같은데, 12,1,2월달은 독재기숙에서 공부하다가 정규반부터...
-
추억보정인지는 몰라도 그때가 제일 재밌었던 것 같음요
-
테슬라야 아프니 9
아프면 좀 참으면 안되니..
-
근데 믿말언제옴 2
그사람없으니까심심하네
-
사실 당뇨 2
뇨자 돌림 이렇게 하는거 맞나요?
-
져도 괜찮아~~ 넘어지면 우때~~
-
사실 여자친구있음뇨 13
뻥임뇨
-
추합 많이 돌 것 같나요? 진학사 전공 보면 메디컬 쓴 사람들 되게 많던데
-
으아..
재밌겠군
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이다.
옙옙