[알고리즘] BOJ 1789번 - 수들의 합(python3)

* 알고리즘 너무 약해서 기초 문제 50개 목표로 푸는 중...

* 3시간 안에 답을 내지 못하면 답지를 보고 30분 내로 정답 판정을 받고, 3일 뒤 다시 풀어보기

---

Greedy

9 / 50(NEW!)

 

탐색

8 / 50

 

기초 동적 프로그래밍

6 / 50

---

투포인터

2 / 10

 

이분탐색

0 / 10

---

문제

https://www.acmicpc.net/problem/1789

1789번: 수들의 합

→ solved.ac 기준 실버 5

---

문제 해결 아이디어

자연수의 합 S에 대하여 자연수 N의 최댓값 구하기

→ 자연수의 합을 구할 때 필요한 값의 갯수가 많도록 하려면 작은 것부터 우선적으로 해야 한다.

→ while 문으로 1부터 차례대로 S를 0미만이 될 때까지 뺀다. 그리고 그 횟수를 -1한 후 제출한다.

만약 5이라고 가정할 때,

5에서 1, 2, 3 까지 빼주면 while문은 중단된다.

이 때 5는 -1이 되어있을 것이다.

이미 뺀 숫자인 1, 2, 3에서 0으로 만들 수 있는 숫자가 하나는 꼭! 있기 때문에 

횟수에 -1를 해준 후 출력한다.

---

구현

내 풀이

import sys
input = sys.stdin.readline

def solution(s):
  if s == 1:
    return 1
    
  answer = 0
  cnt = 1
  
  while s >= 0:
    s -= cnt
    cnt += 1
    answer += 1

  return answer - 1

s = int(input())
print(solution(s))

cnt와 answer를 함께 쓸 수 있음

---

메모

• 걸린 시간: 10분

---