재밌는 문제 풀어보셈요(10.20)(2000덕)
게시글 주소: https://orbi.kr/00069551380
간단한 정수 문제이지만
사실 증명이 메인이라 증명도 간략하게 써주시면 감사하겠습니다!
난이도 :2.5/5
0 XDK (+0)
유익한 글을 읽었다면 작성자에게 XDK를 선물하세요.
-
더프 지구13번 연령축 반대로봄 그래서 그림에 층리면은 서쪽으로 경사지게 그림 근데...
-
ㅆㅆㅆㅆㅆㅆㅆㅆㅆㅆ ㅅ ㅅ ㅅ ㅅ. ㅅ ㅅ ㅅ ㅅ ㅅ ㅅ 기분이 너무 좋다 종익모...
-
원태인 죽이기 뭐냐고 20
진짜
-
션티쌤 사랑해요 0
순삽은 아직 안들어서 다 틀려요 헤헤
-
으
-
그러합니다
-
EBS 주판 지문 수능에 나올 확률 큰가요? 이해하기 어려워서요ㅠㅠ
-
화학 고능아에 항상 존댓말로 친절하게 여러가지 풀이법 설명해주시는 모습이 정말 좋음...
-
흠... 한국식 이름 지어주고 싶다
-
시간없어서 둘다는 못풀고 둘중 하나만 사야할거같은데 뭐사까요
-
사실 저 연의임 12
였으면 좋겠다..하 ㅆㅍ
-
고2 국어 노베 4
고2 국어 노베인데 개념의나비효과 입문편 듣고있거든요? 근데 90강은...
-
빡모 4-2후기 2
확통이고 친구가 시간 부족했다길래 해봤는데 생각보다 너무 쉬웠어서 당황; 22번...
-
원래 하던대로 이번에도 잇올 갈려고 했는데 한번도 기숙학원에 다녀본 적이 없어서...
재밌겠군
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이다.
옙옙