그리디 알고리즘

문제)

입력)

• 첫째 줄에 N(1 <= N <= 100,000)과 K(2 <= K <= 100,000)가 공백을 기준으로 하여 각각 자연수 로 주어집니다.

출력)

• 첫째 줄에 N이 1이 될 때까지 1번 혹은 2번의 과정을 수행해야 하는 횟수의 최솟값을 출력합니다.

시간 제한: 2초 / 메모리 제한: 128MB

---

문제 풀이)

1번.

1번은 단순히 나누어지면 나누고 나눌수 없다면 1을 빼주는 방법이다.
1번 수행할때마다 count 값에 1을 추가해주어 횟수를 구했다.

이때 n 과 k 의 값이 어떻든 k 가 1보다 크다면 1씩 빼는것보다
나누는것이 더 효율적이기 때문.

2번.

target 변수를 지정하여 (n//k) *k = k 가 나누어떨어지면 n 값이 출력되고 안나누어 떨어진다면 n-1 값 이 나오기때문에
count += (n-target) 을 했을때

• 1. 위의 방식으로 1을 뺀 횟수를 알 수 있다.
     1) n이 k에 나누어 떨어지면 count += (n -(n-1)) 이기때문에
     count 에 1을 더해주고
     2) count += (n-n) 이기때문에 안나누어 떨어진다면 카운트가 안된다 3) 1을 뺏다면 n의 값은 n에서 1은 뺀 값이 된다.
• 2. 1이 안빼진다면 나누어 떨어진다는 뜻이므로
     카운트1 을 해주고 n을 k 로 나눈값이 n 의 값이 되며
     if 문을 통해 n < k 즉 k 로 나눌수 없을때 반복문을 탈출
• 3. 반복문을 탈출 한 뒤에 n - 1값을 카운트에 추가한다.
     이때 마지막으로 나누어 떨어졌다면 1이 되기때문에 0이 추가됨.

---

문제2)

입력)

첫째 줄에 여러 개의 숫자로 구성된 하나의 문자열 s가 주어집니다.

출력)

첫째 줄에 만들어질 수 있는 가장 큰 수를 출력 합니다.

입력 예시1)

02984

출력 예시1)

576

입력 예시2)

567

출력 예시2)

210

시간 제한: 1초 / 메모리 제한: 128MB

문제 풀이)

문자열이기때문에 문자열 s를 data 리스트에 int 형으로 변환하여 초기화 시켜주고,
for 문을 통해 data 리스트에 방문하며
data[i] 의 값과 sum 의 값이 1 이하라면 더해주고
아니면 곱해주면 된다.

이때 유의 사항으로 sum 의 값을 포함하지 않으면 sum이 0 이고 입력해야 하는 값이 9 여도 곱연산을 하는데 0이 되기때문에 최대 값을 만족하지못하기 때문.

---

문제 3)

입력)

첫째 줄에 모험가수 n이 주어집니다.
둘째 줄에 각 모험가의 공포도 값을 N이하의 자연수로 주어지며 각 자연수는 공백으로 주어집니다.

출력)

여행을 떠날 수 있는 그룹 수의 최댓값을 출력 합니다.

입력 예시)

5
2 3 1 2 2

출력 예시)

2

시간 제한: 1초 / 메모리 제한: 128MB

문제 풀이)

인원수를 추가하며 인원수 값이 공포도 이상이라면 그룹수에 1을 더하고 인원수 초기화.