재밌는 문제 풀어보셈요(10.20)(2000덕)
게시글 주소: https://orbi.kr/00069551380
간단한 정수 문제이지만
사실 증명이 메인이라 증명도 간략하게 써주시면 감사하겠습니다!
난이도 :2.5/5
0 XDK (+0)
유익한 글을 읽었다면 작성자에게 XDK를 선물하세요.
-
서울대나 연대 경희대 뱃지도 예쁘다 생각했는데 보다보니 건국대랑 동국대가 진짜 예쁜듯
-
처음 들으면 뭐부터 들으면 되나요???
-
ㅎㅋㅎㅌㅋ
-
캬
-
누구 탈릅함? 4
?
-
평가원 교육청은 항상 잘 나오긴 했는데 올해 공부 자체를 열심히 안해서 그런지 요즘...
-
젠지화이팅
-
내가 성적 올린 글에 이런거 달리네 ㅋㅋㅋㅋㅋ 저러면 재밌나 특정 방지를 위해 원글은 삭제함
-
수학 2개 틀렸다는 새끼 놀리니까 부들부들대노 ㅋㅋ 1
그게 접니다 ㅅㅂ 아니 2개 틀려서 1등급 문 닫을줄 알았는데 2등급 문...
-
평가원은 2등급, 가끔씩 미끄러질때 3등급 정도 나오는데 올해 다른 과목이 급하다는...
-
진지하게 사탐은 1
18일도 많이 남아보이는데 내가 이상한건가 ㅋㅋ 개념, 기출 복습하고 실모...
-
5월달 대동제 3일차때 찍은 사진입니다ㅏ! 당시 사학과 친구가 주점 놀러오라고 해서...
-
좆같다~ 2
에휴 개시발
-
물론 공대기준으로 국어 3받아도 ㄹㅇ 서울대 공대 뚫림?
-
안녕하세요 경기 일반고교에 다니는 일반 학생 입니다. 고 1 1학기 성적은 1.04...
-
이해원n제 2
이해원 n제 문제 좋나요 주변에서 다 별로라 하길래요 별로면 하사십이랑 부스터 풀생각입니다
-
1시 전엔 끝나려나 이거 ㅈㅔ발 3대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이다.
옙옙