백준에 있는 알고리즘 문제를 선정한 후 풀이를 해보고자 한다.
1789번 수들의 합
서로 다른 N개의 자연수의 합이 S라고 한다. S를 알 때, 자연수 N의 최댓값은 얼마일까?
조건 : 첫째 줄에 자연수 S(1 ≤ S ≤ 4,294,967,295)가 주어진다.
뭔가 이 문제는 예제 입출력을 보기 전까지는 감자체도 못잡았다. 그러나 예제를 보고 조금은 감을 잡았다.
여기서 자연수 S 즉, N개의 자연수의 합이 200일 시 N은 19라고 했다.
19가 최댓값이고 서로 다른 수라고 했으면 19보다 작은수 18,17,16 등처럼 1만큼 작아지는 수들의 합임을 알 수 있다.
그러나 1~19의 합으로는 200에 모자라고, 다음 수인 20을 더하면 210이 되어 S가 되버린다. 그래서 N는 200을 넘지않는 19가 된다.
1부터 더해가며 만든 합이 S를 초가한 순간 하나씩 더한 숫자 개수 -1 이 N의 최대값이 된다.
s = int(input())
n = 1
while n * (n + 1) / 2 <= s:
n += 1
print(n - 1)
입력 받는 자연수의 합 S를 먼저 쓰고
n은 자연수이니 1이라고 정한다.
그리고while반복문을 쓰는데 그 안의 공식인 n * (n + 1) / 2은 1부터 n까지의 합을 구한 공식이다.
1부터 n까지의 합이 자연수의 합 S보다 작거나 같다면 n += 1을 하는데 아니면 n-1을 출력시킨다
10610번 30
어느 날, 미르코는 우연히 길거리에서 양수 N을 보았다. 미르코는 30이란 수를 존경하기 때문에, 그는 길거리에서 찾은 수에 포함된 숫자들을 섞어 30의 배수가 되는 가장 큰 수를 만들고 싶어한다.
이 문제는 어떤 특정한 수를 입력받은 후 30의 배수가 되는 수로 재정렬 해서 출력하는 문제이다.
30의 배수라는 것은 10과 3의 공통된 배수이면 해당이 되는 것이다. 10의 배수는 끝자리에 0이 오면 되고, 3은 각 자리숫자를 모두 더해서 3의 배수이면 된다.
이 두 조건을 만족하면 되는 것이다.
n = input()
if "0" not in n:
print(-1)
else:
num_sum = 0
for i in range(len(n)):
num_sum += int(n[i])
if num_sum % 3 != 0:
print(-1)
else:
sorted_num = sorted(n, reverse=True)
answer = "".join(sorted_num)
print(answer)
위의 코드에서 첫 if문으로 0이 없는 n은 10의 배수가 못되므로 바로 -1을 출력하게 했다.
else문에서 num_sum이라는 각 숫자의 합을 뜻하는 변수를 만들었고,이 변수를 두번째 if문에선 num_sum의 나머지가 0이 아니면 -1을 출력하게했다.
이 두 코드를 통과한 값은 내림차순으로 정렬시켜주었다.