재밌는 문제 풀어보셈요(10.20)(2000덕)
게시글 주소: https://9.orbi.kr/00069551380
간단한 정수 문제이지만
사실 증명이 메인이라 증명도 간략하게 써주시면 감사하겠습니다!
난이도 :2.5/5
0 XDK (+0)
유익한 글을 읽었다면 작성자에게 XDK를 선물하세요.
-
ㅈㄱㄴ
-
아무리 생각이 없어도 하루도 안돼서 계엄 해제는 못하게 하지 않을까요 뭔가 계획이...
-
개꿀잼 역대급 떡밥이 터져버렸잖아
-
내일 휴강인가요
-
O/X 퀴즈 0
{1, 2, 3, 4}와 같은 유한집합에는 모든 원소가 뽑힐 확률이 같은...
-
ㅇㅅㅇ #~# 4
이모티콘 입니다
-
아 제발 휴일
-
시작했다 1
생방중
-
개회됨 2
ㅇㅇ
-
못 보겠다..
-
라방으로 국회 담넘고 들어가는거 보여줌
-
국회 상황 1
수능끝난 고3교실같네 엄청 시끌시끌해
-
어케됨? 간첩으로 잡아감? 일단 친구들끼리는 윤석열 패드립 뒤지게 박고있긴한데
-
-
아직 300명 안모여서 아직은 ㄱㅇㄹ 효력있는건가요?
-
정치인들 싸우는거 WWE라매ㅋㅋ UFC하고앉아있는데 2
뭔데이게
-
실시간 시위 장면 안봐도 비디오임 ㅇㅅㅇ 과연 12월안에 윤카 탄핵 ㄱㄴ할것인가 ㅋㅋ
-
속보
-
국사에 별로 관심이 없어서 계엄령 선포가 어떤건지 잘 몰랐는지 친구한테 얘기...
-
서울의 봄을 통해 라기엔 투표가 영 아닌데 흠 뭘까
-
무효를 무효 이딴 소리하네 ㅋㅋ
-
한국사 교과서를 보다가 나온 구절이에요
-
바로 지금이 0
좋아요 받고 덕코 수급받는 덕코 버닝이벤트냐
-
상황 아닌가?
-
[속보]계엄군, 국민의힘 정책위의장실 창문 뚫고 진입 1
4일 새벽 국회 상황.
-
190명 모아다가 총살시키나
-
엄
-
정상적인 방법으로는 계엄해제가 되나?
-
???:아 군인은 퇴근이 없구나 ??:너는 왜 말을 그렇게 하냐
-
거짓사진을 쓰네 시청자 제공 ㅇㅈㄹㅋㅋㅋㅋ 이래서 언론이 무서운거
-
중계 1
시위중
-
계엄 선포 시 대통령은 이를 지체없이 국회에 통보하여야 한다. 2
정법 개념입니다~
-
'정우성'이 출현한 '서울의 봄'
-
소화기다 0
.
-
계엄령으로 ㄹㅇ 얻을게 뭐가 있지 이러다가 걍 삼일천하도 아니고 세시간 천하마냥...
-
교수님아 ㅠㅠ
-
다음을 기약할수 있을까 진짜 중요한 순간인데
-
어떻게됨?
-
일단 딸 한 번 치고 생각할까?
-
지난주에 왠지 빌려오고 싶었음뇨
-
-
https://www.youtube.com/watch?v=LJKfbLKmE0A흥미진진
-
어그로성글 하나는끝내줬는데...
-
뭐지
-
충격적인 뉴스네 0
이태원 뉴스 봤을때 느꼈던 그 감정을 다시 느껴보는구나
-
150명 정족수는 채웠는데 지금 특전사가 유리 깨고 진입시도중
-
우원식 의장, 국회 본회의 개의
-
이게 가짜라는걸 모두에게 알립시다
-
-
마치 꿈을 꾸고 있는 듯한
재밌겠군
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이다.
옙옙