[이코테] part 2_2주차_p.201 떡볶이 떡 만들기

 

 

 

 

 

 

 

문제 (출처 : <이것이 코딩 테스트다>)

---

제출한 답

- 입력값 처리 X

N = 4
M = 6
rc = [19,15,10,17]

def isTheRestZero(valueL, M):
    return True if (sum(valueL)-M) % len(valueL)==0 else False
    
valid_rc = list(rc) 
print(valid_rc)
while(not(isTheRestZero(valid_rc, M))): 
    valid_rc.remove(min(valid_rc))   # 최솟값 제거
    print(valid_rc)

answer = (sum(valid_rc)-M) // len(valid_rc)
print(answer)

---

문제 풀이

🔆 문제 요약

• input
  • 첫번째 줄
    • N : 떡의 개수
    • M : 손님이 요청한 떡의 길이
  • 두번째 줄
    • 떡의 개별 높이
      • 떡 높이의 총합은 항상 M임
• output
  • 적어도 M만큼의 떡을 집에 가져가기 위해 절단기에 설정할 수 있는 높이의 최댓값

🔆 예외 사항

방법1. H가 주어졌다는 잘못된 생각

• H와 같거나 작은 수의 떡은 0이 됨
  • H보다 큰 수만 의미있는 값이 됨
• 앞선 예제에서 아래와 같은 방정식이 성립함

19-H+ 15 - H + 17-H=6

-3H=-45

H=15

• 즉 의미있는 값의 개수만큼 N을 설정한 다음
  • 의미있는 값을 모두 더하고 사용자가 설정한 N의 값을 빼줌

방법2.

• 일단 H는 N(손님이 요청한 떡의 길이)이 1이상이므로 가장 큰 값보다 작아야 함
  • H < 떡리스트 최댓값
• 떡 높이의 총합은 항상 M이고 항상 양수
  • 즉 실수가 나올 일은 없음
• ‘적어도 M만큼의 떡’이라는 말은 M이상이어도 상관없다는 뜻(코드에는 못 짬)
  • ex) [17,15,10,17]에서 M=6일 때
    • H=15인 경우 나머지 떡의 길이=4
    • H=14인 경우 나머지의 떡의 길이=7이 나오므로, H는 14가 됨
• 위 방정식을 활용
  • 가장 작은 값은 어차피 0이 될 확률이 높으므로 1차로 제거하기 적당함
  • 리스트 내 모든 값의 합 - M = 리스트 내 원소의 갯수 * H
  • 이 방정식을 통해 나머지가 0인 값을 찾음
  • 물론 나머지가 0이라고 다 정답은 아니므로 직접 떡을 잘라보는 2차적인 작동이 필요

def cutRiceCake(valueL, answer, M): # valueL = 떡리스트, answer = H라고 생각되는 것
    crc = 0
    for v in valueL:
        crc+= 0 if v<=answer else v-answer
    return True if crc==M else False

🔆 기능 사항

• def isTheRestZero(value) : 나머지가 0이면 True 반환
• def cutRiceCake(vlaueL, answer, M): 떡 리스트와 H값을 구해봄
• def run() : 실행하는 메인 함수
  • 현재 리스트의 모든 값의 합을 구함 : allListSum→ sum(list) 내장함수 사용
  • 모든 값의 개수 * H = allListSum - M
    • H = (allListSum-M) % 모든 값의 개수 → H가 0이면 답
    💡 H => (sum(valueL) - M) % len(valueL) == 0
  • 나누어 떨이지는 지 확인
    • 나누어 떨어질 경우 H
    • 나누어 떨어지지 않을 경우 현재 리스트에서 가장 작은 원소 제거 후 다시 반복