재밌는 문제 풀어보셈요(10.20)(2000덕)
간단한 정수 문제이지만
사실 증명이 메인이라 증명도 간략하게 써주시면 감사하겠습니다!
난이도 :2.5/5
0 XDK (+0)
유익한 글을 읽었다면 작성자에게 XDK를 선물하세요.
-
잠뇨 0
ㅂㅂ
-
대학가면 이런것도 알려주나 일단 책이라도 읽어야하는데
-
조회수 대비 업로드 되는 글 수 이게 맞아?
-
프로미스나인 유튜브 존나 봤음
-
꾸덕 바삭한 쿠키가 먹고싶다
-
옯창임?
-
남자아이돌축구GOAT 맛자욱전여자친구GOAT 화이팅!
-
이해가 ㅈ도 안됐음뇨 ㄹㅇ
-
https://youtu.be/rx6gz2I_suk?si=F7ltEkRc_jjWSiN...
-
내신 별로 안남았긴했는데 자료가 너무없어서,,1년에 5만원이고 사람모일때마다...
-
야식에 혼술 4
이때가 요즘 내가 제일행복한 순간일듯
-
장카설유 안민윈카 12
몇 명 빼고 그 자리에 정은비 이채영 강해린 넣어야 됨
-
하
-
어떻게일어나지?
-
윤석열을 타도하자같은 이런게 진짜 존재한거었나요 ㄷㄷ..
-
심연을 들여다보자
-
앞으로도 즐거운 시간 보내요
-
야식ㅇㅈ 3
-
설뱃 갖고싶다
-
멈춰야 하는 것 정신건강에 좋지않아요
-
결국 혼자다 혼자 ~
-
이번에 로지텍 무선마우스 자동충전해주는 패드 5만원에 핫딜 하던데 사고싶음......
-
잠이 안 오네 중간중간 깨긴했는데 나도 내가 15시간을 잘줄은 몰랐지
-
하... 다들 잘자요
-
가운데를 크게 벗어나지 않네
-
나중에 끄면 아무도 없다는 게 슬픔뇨
-
너 외향적이지? 2
-
늙어서 점차 꺾인건지 소신을 유지하고픈 마음보다 주변 사람에게 미움받을 무서움이 더 크다
-
자퇴의 최대 장점 13
https://youtu.be/7fy1eFEkrpU?feature=shared 이...
-
캔맥에 짜파게티랑 10
김치먹을예정
-
ㅇㅈ 8
-
수험생활시절 많은 도움을 얻었던 오르비 시간은 흘러 어느덧 28살이되었고 좋은학교...
-
사실은 12
아직 어플도 안 깐 범부입니다 그동안 크롬을 애용했음뇨
-
정치테스트 해보니 내가 되게 보수적이었다는 걸 깨달음
-
9모때 시대만 블랭크 맞췄다그래서 ㅈㄴ불안하네
-
아직 재밌는데 몸이 안 받아주네
-
악 월급 들어왔다 16
기쁨의 랜덤 덕코 분수쇼
-
ㄹㅇ 지금 소신껏 일하면 조리돌림 당해요??
-
-
-
-
본인이 현실에서 위축되는 사람이지만 가상공간에서는 적극적으로 자기표현하는 사람에...
-
난 pc방데이트
-
옯창들 점수 구경 좀 해볼까? 어 씨!발 눈에 보이는 건 5등급 플마단
-
화1 부활 기원
-
대신 지워줄 사람
-
문과 조지기 들어가는 평가원
-
꼭 내향형 나온사람 손들어보라 하면 아무도 안 들었어요 ㅋㅋ 그땐 다들 내향형...
-
예비고3입니다 현재 메가패스 끊어둔 상태고 수능때 화1생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이다.
옙옙