재밌는 문제 풀어보셈요(10.20)(2000덕)
게시글 주소: https://orbi.kr/00069551380
간단한 정수 문제이지만
사실 증명이 메인이라 증명도 간략하게 써주시면 감사하겠습니다!
난이도 :2.5/5
0 XDK (+0)
유익한 글을 읽었다면 작성자에게 XDK를 선물하세요.
-
참고로 수능 기출 문제임
-
2024년 10월 2주차 韓日美全 음악 차트 TOP10 (+10월 1주차 주간VOCAL Character 랭킹) 6
2024년 10월 1주차 차트: https://orbi.kr/00069503208...
-
주류문화도 반문화,하위문화 처럼 전체사회의 문화적 다양성 증진에 기여하나요?
-
해보고싶었어요..
-
훈쌤커리만 타서 그런가
-
오랜만에 치유물로 힐링하고 싶음
-
점심먹고 식곤증 2
학교에서 점심먹으면 식곤증이 좀 심하게 오는데 어떻게 극복해야되나요?? 이거때메 미치겠네요
-
웬만한 쉬4 는 풀겠는데 10모 수학 21 22 같은 문제들을 손댈수는 있는데 막상...
-
8884888각 4
ㅋ
-
호빵 취향 8
고기 호빵이랑 야채호빵 맛있음
-
9평 국어 95 (독서 2틀) 이후 파이널 대비 실모 기록 상상 파이널1 제2차 -...
-
언매랑 독서는 막 크게 다르진 않으니까 그렇다 치고 문학에서는 무슨 차이라고...
-
절대 제가 못봐서 물어보는건 아니구요.. 네..
-
흠
-
요즘 수능 경제 공부자료를 올리면서 그냥 ‘경제’ 검색을 많이 햐보는데요 혹시나...
-
듣기는 기출 풀고있는데 응답쪽에서 두개정도 자꾸 틀립니다.. 뭐해야할까요
재밌겠군
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이다.
옙옙