글 읽기 - 성냥 개비 최솟값 결과가 잘못된 것 같은데 어떤 방향으로 해결해야 하나요?

(追記) (追記ここまで)

성냥 개비 최솟값 결과가 잘못된 것 같은데 어떤 방향으로 해결해야 하나요?

3687번 - 성냥개비

spdlqjdk1012 4년 전 0

성냥 개비 최솟값 결과가 잘못된 것 같은데 어떤 방향으로 해결해야 하나요?

minDP[100] = 188888888888888<-정답 1000000000<-결과

우선 반례는 찾았으나 로직을 어떻게 고쳐야할지 잘 모르겠습니ᅡᄃ

INF = int(1e9)
# 0~100 까지 인덱스 초기화, 성냥개비100개
minDP = [INF for _ in range(100+1)] 
minDP[2] = 1 # 성냥개비 2개로 만들 수 있는 최소값
minDP[3] = 7
minDP[4] = 4 
minDP[5] = 2
minDP[6] = 6 # 숫자는 0으로 시작할 수 없다
minDP[7] = 8
minArray = [INF, INF, 1, 7, 4, 2, 0, 8]
for i in range(8, 101):
 for j in range(2, 8):
 minDP[i] = min(minDP[i], int(str(minDP[i-j])+str(minArray[j])))
#minDP[100] = 188888888888888<-정답 1000000000<-결과
maxDP = [0 for _ in range(100+1)] 
maxDP[2] = 1 # 성냥개비 2개로 만들 수 있는 최대값
maxDP[3] = 7 # 성냥개비 3개로 만들 수 있는 최대값
for i in range(4, 101):
 num = i
 if num % 2 == 0:
 maxDP[i] = int('1' * (num // 2))
 else:
 maxDP[i] = int('7'+('1' * ((num // 2)-1)))
minresult = []
maxresult = []
tcase = int(input())
for i in range(tcase):
 N = int(input())
 minresult.append(minDP[N])
 maxresult.append(maxDP[N])
for i in range(len(minresult)):
 print(minresult[i], maxresult[i])

wldnr1014 1년 전 0

int형으로 받아줘서 최대값을 넘어가서 그런거 아닐까요?

댓글을 작성하려면 로그인해야 합니다.

(追記) (追記ここまで)

Baekjoon Online Judge

채점 현황

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말

사업자 등록 번호: 541-88-00682
대표자명: 최백준
주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
전화번호: 02-521-0487 (이메일로 연락 주세요)
이메일: contacts@startlink.io
통신판매신고번호: 제 2017-서울서초-2193 호

한국어 | English (Beta)

문제

문제

출처

ICPC

성냥 개비 최솟값 결과가 잘못된 것 같은데 어떤 방향으로 해결해야 하나요?

spdlqjdk1012 4년 전 0

wldnr1014 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말