재밌는 문제 풀어보셈요(10.20)(2000덕)
간단한 정수 문제이지만
사실 증명이 메인이라 증명도 간략하게 써주시면 감사하겠습니다!
난이도 :2.5/5
0 XDK (+0)
유익한 글을 읽었다면 작성자에게 XDK를 선물하세요.
-
식센모 ㅊㅊ 6
시즌1 2 파이널 이렇게 3개 있던데 이 시즌은 꼭 풀어라하는 강추하는 시즌있나요...
-
선데이 하이 5
-
화미쌍윤 국어 낮1 수학 2 탐구 만점 어디가 가능할까요? 문과에여
-
공부하기힘든듯 그래도 좋은대학갈라면 공부를 해야되니 남들보다 시간을 두배로 더써야함...
-
치매걸리신 할머니께서 아들분 이름부르면서 어디가 같이가 이러시는데 마음이 미어진다..너무 슬퍼 ㅠㅠ
-
제주대 교대에서 경기도로 임용되는것 어렵나요?
-
음 역시이쁘군
-
본인 얼굴이 빻았다면 연애상상은 하지마십쇼.기대치가 올라가면 좌절감이 심해집니다.
-
벌써부터 ㅈ같네 고졸 신분으로 1일 8시간 꽉 채워서 주4~5회 할 수 있는 알바...
-
베이스 정도는 만들기 충분한 시간인가요? 국어 4 수학 4 영어 5 사탐 개념...
-
법 좋아해서 변호사 쪽으로 가고싶은데 주위에서 너 말도 잘 못하고 글도 잘 못 쓰지...
-
이라고 테스형이 그랫슴
-
방송국은 회사이니 비공식 조직 아닌가요?
-
현재 상황 직장인 하루 학업가능량 평균적으로 볼때 주말포함하면 매일 6시간 전후인데...
-
공군탄약올만함 4
바이럴구라아님
-
나 수학 잘하는 편이 아닌데 왤케 높게 나오지
-
더 많은 무료 고난도 문제는 https://t.me/JerryEthic
-
음 왤까
-
님들근데 내년부터 교육부에서 사탐런막으면 입시판 정상화되는거임? 4
사탐런없으면 과탐정상화될거같은데
재밌겠군
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이다.