재밌는 문제 풀어보셈요(10.20)(2000덕)
게시글 주소: https://orbi.kr/00069551380
간단한 정수 문제이지만
사실 증명이 메인이라 증명도 간략하게 써주시면 감사하겠습니다!
난이도 :2.5/5
0 XDK (+0)
유익한 글을 읽었다면 작성자에게 XDK를 선물하세요.
-
웹툰이나 인스타같은거 그냥 쉴 때 잠깐 보니까 괜찮겠지 했는데 뭔가 그 날 공부한...
-
결국 다이소도 내놨다...2천 원짜리 두바이 초콜릿 '화제' 2
고가에도 불구하고 선풍적인 인기를 끈 '두바이 초콜릿'을 다이소가 저렴한 가격의...
-
제 아이디 입력해주시면 추천해주신 분과 제게 모두 만원권이 증정된다고 합니다!...
-
물리하다 젖음요
-
정보가오ㅑㄹ케없지
-
개멍청해보여서 한대 쥐어박고 싶음 넘기엽따
-
강k국어 등급컷 알고 계신분 있으신가요ㅠㅠ? 몇회차 상관없이 아시는 것만이라도 좀...
-
문학 시간줄이기 0
다들 문학 문제랑 동시에 보면서풂? 다시 서칭하러 가는시간 개 오래 걸리는것같아서
-
수학 극한 질문 2
20번 해설에서 fx가 왜 x-3을 홀수개 가져야지 발산하나요? 짝수개여도 0인자가...
-
다른 실모 풀면 92-88정도 나오는데 이해원 모고만 풀면 70점대를 박아버네.....
-
미적분 선택자고요, 미적분파트는 1-2번부터 반은 찍고 들어가는 수준으로 개념...
-
이감 바탕처럼 패키지로 사야하는거 말고.. 5회분정도 들어있는 봉투모고 추천해주세요
-
ㄷㄷ
-
신경 안쓰시나요?? 요즘 실모치면 잘보고 못보고를 반복하는거같은데…
-
독서할시간에문학할까요
-
냄새.. 난다고오....
재밌겠군
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이다.
옙옙