AndroidTeacher

www.acmicpc.net/problem/2217

문제 설명

N개의 로프를 이용해 물체를 들어올린다.

N개의 로프는 주어진 중량만큼까지만 물체를 들어올릴 수 있으며, K개의 로프를 이용하여 W무게의 물체를 들어올린다면, 모든 로프에 똑같이 W / K 만큼의 중량이 걸리게 된다.

입력으로 각 로프들에 대한 정보가 주어지면, 이 로프들을 이용하여 버틸 수 있는 최대 중량을 출력하면 된다.

풀이 과정

A라는 로프가 버틸 수 있는 중량이 최대 A라면 이 로프는 A를 넘어가는 무게는 들 수 없다.

이 때, A 한개를 이용하면 A만큼 들 수 있고 두개를 이용하면 2A만큼 들 수 있다. ( 2A / 2 = A )

주의해야 할 점은, 가장 무거운 무게의 로프가 들 수 있는 중량을 A, 그 다음을 B라고 할 때,

로프 1개를 이용하여 들수 있는 중량의 최댓값은, A가 될 것이고, 로프 2개를 이용하여 들 수 있는 최댓값은 B*2가 된다.

즉, 이용할 로프 중 가장 작은 무게의 로프중량 * 개수 가 될 것이다.

따라서, 로프의 개수를 늘릴수록 최댓값은 그 로프의 무게*N이 될 것이기 때문에

로프들의 무게를 내림차순으로 정렬하여, 로프의 개수가 늘어갈수록 현재 로프의 수 * 쌓인 로프의 수를 곱해주면 로프들이 들 수 있는 무게의 값들이 정리될 것이다.

n = int(input())
rope = []

for i in range(n):
    rope.append(int(input()))
rope.sort(reverse=True)

for i in range(n):
    rope[i] = rope[i] * (i+1)

print(max(rope))

https://github.com/HongEunho

전체 문제 & 코드는 위의 깃에 정리되어 있습니다.

팔로우 & 맞팔은 환영입니다 !

www.acmicpc.net/problem/13305

문제 설명

N개의 도시가 일렬로 나열되어 있고, 각 도시간의 거리를 입력받는다.

그리고 그 도시에서의 리터당 주유비를 입력받는다.

이 때, 도시의 시작점에서 끝지점까지 이동하는데 드는 최소의 비용을 구하면 된다.

풀이 과정

각 도시마다 주유소의 가격이 다르기 때문에, 최소의 비용으로 최대충전을 하는 것이 목표다.

이 때, 시작점에서는 반드시 주유가 되어있어야 하기 때문에 첫 최소비용은 시작점의 가격으로 시작한다.

이동을 하다가, 현재의 가격보다 저렴한 도시를 발견하게 되면, 그 지점에서 충전을 이어서 하면 되고

현재 가격보다 저렴한 도시가 나타나지 않는다면, 현재 가격으로 계속 충전하면 된다.

혹여나, "미리 충전을 해야하는데 어떻게 이동중에 전 가격으로 충전을 하냐"고 생각을 할 수 있는데

for문을 통해 dis[i]는 계속해서 다음 이동 거리로 변하는 상황이고

다음 최저 가격이 등장하기 전까지는 이전 최저가격을 저장하고 있는 상황이기 때문에 이 방법이 가능하다.

코드를 보면 더 이해하기 쉬울 것이다.

n = int(input())

dis = list(map(int, input().split()))
price = list(map(int, input().split()))

minPrice = price[0]
ans = 0
for i in range(n-1):
    if minPrice > price[i]:
        minPrice = price[i]
    ans += minPrice * dis[i]

print(ans)

https://github.com/HongEunho

전체 문제 & 코드는 위의 깃에 정리되어 있습니다.

팔로우 & 맞팔은 환영입니다 !

www.acmicpc.net/problem/1541

문제 설명

수식이 문자열로 주어질 때, 적절한 괄호를 쳐서 수식의 결과값을 최소로 만들면 된다.

단, 처음과 숫자는 숫자이며, 두 개 이상의 연산자가 나타나지 않으며(++,--) 연산자는 +, -만 사용할 수 있다.

풀이 과정

그리디 알고리즘 문제이다. 최소값을 만들기 위해선 어떻게 해야할까?

마이너스 바로 뒤에 괄호를 열고 그 안의 수식을 최대로 만든 후 다시 괄호를 닫으면 된다.

처음 풀었던 방법은 바로 아래의 코드인데, 마이너스를 만나면 즉시 괄호를 열고, 그 뒤의 마이너스를 만나면 다시 괄호를 닫는 식으로 하여 해결하였다. 그리고 결과값을 eval함수를 이용하여 출력하였다.

정답은 정상적으로 잘 출력되었지만 백준에서 정답을 돌렸을 때, Syntax Error가 발생하였다.

왜냐하면 eval함수안에서 1,3,5등 일반적인 숫자는 잘 인식하지만 01, 001등 앞에 0이 붙은 수는 인식하지 못한다.

그래서 에러가 발생하였다. (문제에서 수는 0으로 시작할 수 있다고 하였음)

exp = input()
ans = ''

flag = 0 # 괄호 열기전
for i in range(len(exp)):
    if exp[i] == '-':
        if flag == 0:
            ans += exp[i]
            ans += "("
            flag = 1
        else:
            ans += ")"
            ans += exp[i]
            ans += "("
    else:
        ans += exp[i]

if flag == 1:
    ans += ")"
print(ans)
print(eval(ans))

그래서 다른 방법을 고안하였고, 코드는 다음과 같다.

먼저 -를 기준으로 문자열을 분리해 준다. 이렇게 되면 첫번째 인덱스를 제외한 각각의 분리된 수식의 앞에는 -가 붙는다는 이야기가 된다.

그래서 첫번째 인덱스의 숫자만 더해주고 나머지 인덱스의 수들은 모두 빼주었다.

이렇게 해서 Syntax Error없이 통과할 수 있었다.

exp = input().split("-")
ans = 0
for i in exp[0].split("+"):
    ans += int(i)

for i in exp[1:]:
    for j in i.split("+"):
        ans -= int(j)

print(ans)

https://github.com/HongEunho

전체 문제 & 코드는 위의 깃에 정리되어 있습니다.

팔로우 & 맞팔은 환영입니다 !

www.acmicpc.net/problem/11399

문제 설명

ATM기 앞에 사람이 N명 서있는데, 이 N명의 사람들이 돈을 인출하는데 걸리는 시간은 제각각이다.

이 때, 앞 사람의 돈을 뽑는 시간이 길 수록, 뒤에 있는 사람들의 대기 시간은 길어지게 된다.

각 사람이 돈을 인출하는데 필요한 시간(대기시간+뽑는시간)의 합의 최솟값을 구하면 된다.

풀이 과정

내가 ATM기에 줄을 서 있다고 가정해보자. 나의 대기시간이 짧아지려면 어떤 상황이 되어야 하는가?

당연히 내 앞에서 돈을 뽑는 사람들이 돈을 빨리빨리 뽑아주면 된다.

즉, 돈을 뽑는 시간이 짧은 사람들 부터 앞에 오도록 하면 된다.

따라서, 시간순으로 정렬을 한 후에 모든 사람들의 시간을 합하면 정답이 된다.

n = int(input())
arr = list(map(int, input().split()))
arr.sort()

ans = 0
for i in range(n):
    ans += arr[i]
    arr[i] = ans

print(sum(arr))

https://github.com/HongEunho

전체 문제 & 코드는 위의 깃에 정리되어 있습니다.

팔로우 & 맞팔은 환영입니다 !

www.acmicpc.net/problem/1931

문제 설명

한 개의 회의실에서 N개의 회의가 이루어진다.

각각의 회의 I에 대해 시작시간과 끝나는 시간이 주어지며, 각 회의실은 겹쳐서 사용할 수 없다.

단, 끝나는 즉시 다음 회의가 시작을 이어받을 수 있으며, 시작 시간과 끝나는 시간이 같을 수도 있다.( 시작 즉시 종료 )

이 때, 열릴 수 있는 회의의 최대 갯수를 구하면 된다.

풀이 과정

대표적인 그리디 개념을 이용하는 문제이다.

그리디는 당장의 상황을 기준으로 확장시키는 방향으로 풀면 쉽게 해결이 가능한 경우가 많다.

내가 회의실을 사용하고 있다고 가정했을 때, 내 회의가 끝난 후에 회의실에서 가장 많은 회의가 열리기 위해서는 어떤 상황이 되야할까? 바로. 내 회의가 빨리 끝나야 하는 것이다. 즉, 종료 시간이 빨라야 한다.

여기서 한가지 더 고려해야 할 점은 바로 종료시간이 같은 경우이다.

예를 들어, (10, 10) 의 회의와 (9,10)회의가 있을 때, 둘의 종료 시간은 같지만, (9,10)를 먼저 선택하면, (10,10)의 회의를 선택할 기회가 주어진다. 하지만, (10, 10)의 회의가 먼저 선택되면, 종료시간이 10을 넘어갔기 때문에 9시작은 고려되지 않는다.

따라서 시작시간으로 먼저 정렬을 해준 후에, 종료 시간을 기준으로 정렬을 해준다.

이렇게 정렬을 한 후에, 종료 시간을 꼬리잡기 식으로 이어나가면 최대 개수를 구할 수 있게 된다.

n = int(input())
room = []

for i in range(n):
    a, b = map(int, input().split())
    room.append([a, b])

room.sort(key = lambda x: x[0])
room.sort(key = lambda x: x[1])

cnt = 1
end = room[0][1]
for i in range(1, n):
    if room[i][0] >= end:
        cnt += 1
        end = room[i][1]

print(cnt)

https://github.com/HongEunho

전체 문제 & 코드는 위의 깃에 정리되어 있습니다.

팔로우 & 맞팔은 환영입니다 !

www.acmicpc.net/problem/11047

문제 설명

N종류의 동전으로 K원을 만들 때, 동전 개수의 최솟값을 구하는 문제이다.

풀이 과정

먼저 coin 리스트에 코인들을 오름차순으로 입력받게 되는데, 가장 적은 수의 코인을 갖기 위해서는 단위가 큰 코인부터 채워야 한다. 따라서 coin을 내림차순 정렬해주고 하나씩 차례대로 계산을 해주면 된다.

K원을 현재 코인으로 나눈 값의 몫을 누적해서 개수로 추가해주고 나머지는 다음 계산을 위해 저장한다.

n, k = map(int, input().split())
coin = []
for i in range(n):
    coin.append(int(input()))

coin.sort(reverse=True)
count = 0
wallet = 0

for i in coin:
    count += k // i
    k = k % i

print(count)

https://github.com/HongEunho

전체 문제 & 코드는 위의 깃에 정리되어 있습니다.

팔로우 & 맞팔은 환영입니다 !