둔필승총

 강남역에 엄청난 폭우가 쏟아진다고 가정합시다. 정말 재난 영화에서나 나올 법한 양의 비가 내려서, 고층 건물이 비에 잠길 정도입니다.

 그렇게 되었을 때, 건물과 건물 사이에 얼마큼의 빗물이 담길 수 있는지 알고 싶은데요. 그것을 계산해 주는 함수 trapping_rain을 작성해 보려고 합니다.

 함수 trapping_rain은 건물 높이 정보를 보관하는 리스트 buildings를 파라미터로 받고, 담기는 빗물의 총량을 리턴해 줍니다.

 예를 들어서 파라미터 buildings로 [3, 0, 0, 2, 0, 4]가 들어왔다고 합시다. 그러면 0번 인덱스에 높이 3의 건물이, 3번 인덱스에 높이 2의 건물이, 5번 인덱스에 높이 4의 건물이 있다는 뜻입니다. 1번, 2번, 4번 인덱스에는 건물이 없습니다.

그러면 아래의 사진에 따라 총 10 만큼의 빗물이 담길 수 있습니다. 따라서 trapping_rain 함수는 10을 리턴하는 거죠.

이번에는 파라미터 buildings로 [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]가 들어왔다고 합시다. 그러면 아래의 사진에 따라 총 6 만큼의 빗물이 담길 수 있습니다. 따라서 trapping_rain 함수는 6을 리턴하는 거죠

이 정보를 기반으로, trapping_rain 함수를 작성해 보세요!

예시

# 테스트
print(trapping_rain([3, 0, 0, 2, 0, 4]))
print(trapping_rain([0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]))

10
6

[해설]

빗물이 담기는 양을 계산하려면 각각의 index에 해당하는 빗물의 양을 모두 더하면 된다. 각각의 index에 빗물의 양을 계산하려면 규칙을 파악해야 한다. 

 먼저 예시를 보고 알 수 있는 점은 0번 인덱스와 마지막 인덱스에는 빗물이 담길 수 없다. 그리고 더 큰 건물들 사이에 끼어 있으면 빗물이 담긴다는 것을 알 수 있다. 그리고 구해야 할 것은 얼마의 빗물이 담기는지 알아야 된다.

다음 그림에서 4번 인덱스를 보자. 4번 인덱스는 왼쪽으로 가장 높은 건물은 3번 인덱스에 있고, 4번 인덱스의 오른쪽으로 가장 높은 건물은 7번 인덱스에 있다. 3번 인덱스의 건물은 높이가 2이고, 7번 인덱스의 건물은 높이가 3인다. 그리고 4번 인덱스에 담긴 빗물의 양은 1이다. 

물이 담기는 것은 4번 인덱스 건물의 높이인 1부터 시작해서, 3번 인덱스와 7번 인덱스의 건물 중 더 낮은 높이인 2까지이다. 그래서 1 만큼의 빗물만 담기는 것이다. 

1. 현재 인덱스의 왼쪽에서 가장 높은 건물의 높이를 구한다.

2. 현재 인덱스의 오른쪽에서 가장 높은 건물의 높이를 구한다.

3. 왼쪽과 오른쪽에서 구한 최대값은 2개인데 이 중 더 낮은 건물의 높이를 구한다.

4. 그 높이에서 현재 인덱스에 있는 건물의 높이를 뺀다.

def trapping_rain(buildings):
    total=0
    for i in range(1,len(buildings)-1):
        max_left=max(buildings[:i])
        max_right=max(buildings[i:])

        upper_bound = min(max_left,max_right)

        total += max(0,upper_bound-buildings[i])
    return total
# 테스트
print(trapping_rain([3, 0, 0, 2, 0, 4]))
print(trapping_rain([0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]))

www.acmicpc.net/problem/2798

문제

카지노에서 제일 인기 있는 게임 블랙잭의 규칙은 상당히 쉽다. 카드의 합이 21을 넘지 않는 한도 내에서, 카드의 합을 최대한 크게 만드는 게임이다. 블랙잭은 카지노마다 다양한 규정이 있다.

한국 최고의 블랙잭 고수 김정인은 새로운 블랙잭 규칙을 만들어 상근, 창영이와 게임하려고 한다.

김정인 버전의 블랙잭에서 각 카드에는 양의 정수가 쓰여 있다. 그 다음, 딜러는 N장의 카드를 모두 숫자가 보이도록 바닥에 놓는다. 그런 후에 딜러는 숫자 M을 크게 외친다.

이제 플레이어는 제한된 시간 안에 N장의 카드 중에서 3장의 카드를 골라야 한다. 블랙잭 변형 게임이기 때문에, 플레이어가 고른 카드의 합은 M을 넘지 않으면서 M과 최대한 가깝게 만들어야 한다.

N장의 카드에 써져 있는 숫자가 주어졌을 때, M을 넘지 않으면서 M에 최대한 가까운 카드 3장의 합을 구해 출력하시오.

입력

첫째 줄에 카드의 개수 N(3 ≤ N ≤ 100)과 M(10 ≤ M ≤ 300,000)이 주어진다. 둘째 줄에는 카드에 쓰여 있는 수가 주어지며, 이 값은 100,000을 넘지 않는 양의 정수이다.

합이 M을 넘지 않는 카드 3장을 찾을 수 있는 경우만 입력으로 주어진다.

출력

첫째 줄에 M을 넘지 않으면서 M에 최대한 가까운 카드 3장의 합을 출력한다.

예제 입력 1

5 21

5 6 7 8 9

예제 출력 1

21

예제 입력 2

10 500

93 181 245 214 315 36 185 138 216 295

예제 출력 2

497

[문제 해설]

먼저 해볼 수 있는 생각은 카드를 3개 뽑아서 m을 넘지않는 수를 뽑는 것이다. 간단하게 3중 포문을 돌려서 3개의 카드가 같지 않고 m을 넘지 않을때 값을 저장해 둔다. 이 값들 중 최대의 것을 뽑으면 된다. m보다 작은 값이 나올 수도 있으므로 나온 값들 중 최대를 뽑으면 되는것이다.

1. m을 넘는 경우 출력을 안하는 것을 생각해 주어야 한다.

2. 3중 for문을 돌릴 때 3개가 동일한 값이 들어가면 안되니까 조건을 추가해준다.

n,m = map(int,input().split())
cards=list(map(int,input().split()))
answer=0
for i in cards:
    for j in cards:
        for k in cards:
            if i!=j and i!=k and j!=k:
                sum=i+j+k
                if sum>m:
                    continue
                else:
                    answer=max(answer,sum)
print(answer)

 Brute-Force Attack은 우리말로 무차별 대입 공격이란 뜻이다. 이 말은 정말 무차별적으로 모든 방법을 시도하는 것을 뜻한다. Brute-Force 알고리즘도 비슷하다.

 예를 들어 자물쇠 0~99까지 가능하다면 0부터 99까지 모든 경우의 수를 시도하는 것이다. 힘들긴 하겠지만 시간만 있다면 가능한 것이다. 브루트 포스는 말 그대로 가장 순진한 알고리즘 접근법이다. 가능한 모든 조합을 찾아서 계산하면 되는 것이다.

 브루트 포스 알고리즘은 모든 경우의 수를 봐서 확실한 답을 구한다는 장점이 있지만 알고리즘 자체는 비효율적이다. 특히, input이 클수록 더 비효율적이라는 생각이 들것이다. 

 브루트 포스는 직관적이고 명확하고 답을 확실하게 찾을 수 있다는 장점이 있다. 그래서 효율적인 알고리즘의 첫 시작은 브루트 포스이기때문에 알고리즘을 배울 필요가 있는 것이다.

아래에 있는 브루트 포스 알고리즘의 예시를 보자.

[문제 설명]

카드 두 뭉치가 있습니다.

왼쪽 뭉치에서 카드를 하나 뽑고 오른쪽 뭉치에서 카드를 하나 뽑아서, 두 수의 곱이 가장 크게 만들고 싶은데요. 어떻게 하면 가장 큰 곱을 구할 수 있을까요?

함수 max_product는 리스트 left_cards와 리스트 right_cards를 파라미터로 받습니다.

left_cards는 왼쪽 카드 뭉치의 숫자들, right_cards는 오른쪽 카드 뭉치 숫자들이 담겨 있고, max_product는 left_cards에서 카드 하나와 right_cards에서 카드 하나를 뽑아서 곱했을 때 그 값이 최대가 되는 값을 리턴합니다.

def max_product(left_cards, right_cards):
	print(max_product([1, 6, 5], [4, 2, 3]))
	print(max_product([1, -9, 3, 4], [2, 8, 3, 1]))
	print(max_product([-1, -7, 3], [-4, 3, 6])) 

[풀이과정]

 브루트 포스 방법으로 for문을 2개 사용하여 풀면 된다. 처음에 max를 사용하여 left_cards 와 right_cards에서 하나씩 최대값을 뽑아서 곱했는데 그러면 음수와 음수의 곱이 최대가 될 경우를 생각못할 수 있다. 

그래서 일일이 다 구해서 최대값을 구하면 된다.

[해답]

def max_product(left_cards, right_cards):
    bigg=0
    for left_card in left_cards:
        for right_card in right_cards:
            wow = left_card*right_card
            if wow>bigg:
                bigg=wow
    return bigg
# 테스트
print(max_product([1, 6, 5], [4, 2, 3]))
print(max_product([1, -9, 3, 4], [2, 8, 3, 1]))
print(max_product([-1, -7, 3], [-4, 3, 6]))

#Tip#

3중 반복문에서 3번째 반복문을 실행 후 2번째 반복문을 다시 실행하는 과정을 재귀로 구현한 코드에서 현재 실행 중인 함수를 호출한 곳으로 돌아가는 과정으로 비유하면 백트래킹 기법을 적용했다고 한다. 백트래킹을 브루트 포스를 수행하는 방법 중 하나로 본다.