재밌는 문제 풀어보셈요(10.20)(2000덕)
게시글 주소: https://orbi.kr/00069551380
간단한 정수 문제이지만
사실 증명이 메인이라 증명도 간략하게 써주시면 감사하겠습니다!
난이도 :2.5/5
0 XDK (+0)
유익한 글을 읽었다면 작성자에게 XDK를 선물하세요.
-
시험 못 봐서 속상해할때 시험이 전부는 아니다고 위로하는건 3
핀트를 못 잡는 위로인게 시험을 못 본게 서러운게 아니라 자기가 가장 바라고...
-
-
이명학 실모 5회풀다가 버릴까말까 고민중임ㅇㅇ
-
2024년 2월 24일 9시 30분부터 12시 30분까지 치러진 도쿄공업대학...
-
재수하고 6평에 99뜨고 이감도 90점대 뜨는데 뭔가 한번 개안을...
-
찐따라서.. 이건 핵존잘이 아니면 극복 불가능함
-
인간다움을 느껴 남의 눈에 좋은 사람이기 전에 나 자신한테 먼저 화해를 청해...
-
난 내가 문학은 잘하는데 독서를 못해서 등급이 안오른다고 생각했는데 이감풀때 독서가...
-
둘다 14번에 지수로그 변주해서 10번 삼각함수 14번 도형 20번 정수조건 ㄷㄱㅈ
-
실린더 속 기체 부분압력이면 옆에 강철용기에 포함된 c는 고려안하는건가요?...
-
자꾸 국어 수학한다고 뒷전으로 밀리니까 답이 없어지네...내년에 열심히 해야지 퓨ㅠ
-
언제 끝나냐 ㅋㅋㅋ
-
-
이제 진짜 추워진듯 18
과잠 입어야겠네
재밌겠군
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이다.
옙옙