반응형

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

 

14500번: 테트로미노

폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변

www.acmicpc.net

문제 설명

링크에서 알 수 있듯이,

좌표 크기 N x M을 입력받은 후에 각각의 좌표 칸 마다 숫자를 부여한다.

 

그리고 우리가 흔히 해봤던 테트리스 게임의 블록 모양들을 이 좌표 위에 올려놓게 되는데

블록이 위치하는 좌표의 숫자들의 합이 최대가 되는 값을 구하면 된다.

즉, 내가 ㅡ(일자 막대) 모양의 블록을 (0,0) (0,1), (0,2), (0,3) 좌표 위에 올려놓았다면

이 네 좌표의 숫자 값을 모두 더해 저장해놓은 후에 이러한 값들의 최댓값을 구하면 되는 것이다.

 


풀이 과정

이 문제는 브루트 포스(Brute-Force) 유형의 구현 문제이다.

모든 칸에 대해 검사를 해보아야 한다.

문제에서 주어진 맵의 크기가 상대적으로 작기 때문에 (4 ≤ N, M ≤ 500)

모든 블록을 모든 칸에 대해 검사하는 방법으로 해결하였다.

 

1. 모든 블록 모양을 각각의 함수로 만든다.

2. 모든 좌표 칸 마다 각각의 함수들의 결과값을 구해 최댓값을 구한다.

 

이 방법 외에도, 모든 블록모양을 담을 수 있는 큰 크기의 2차원 배열을 선언하여

2차원 배열안에 0과 1로 블록 모양을 지정해주는 방식도 있다.

 

편한 방법으로 문제를 해결하면 될 것 같다.

 

코드는 다음과 같다.

n, m = map(int,input().split())
graph = []
ans = 0

def shape1(i, j): # ㅡ
    if j+3 >= m:
        return 0
    return graph[i][j] + graph[i][j+1] + graph[i][j+2] + graph[i][j+3]

def shape2(i, j): # ㅣ
    if i+3 >= n:
        return 0
    return graph[i][j] + graph[i+1][j] + graph[i+2][j] + graph[i+3][j]

def shape3(i, j): # L모양
    if i+2 >= n or j+1 >= m:
        return 0
    return graph[i][j] + graph[i+1][j] + graph[i+2][j] + graph[i+2][j+1]

def shape4(i, j): # L모양 대칭
    if i+2 >= n or j-1 < 0:
        return 0
    return graph[i][j] + graph[i+1][j] + graph[i+2][j] + graph[i+2][j-1]

def shape5(i, j): # L모양 시계방향 회전
    if i-1 < 0 or j+2 >= m:
        return 0
    return graph[i][j] + graph[i-1][j] + graph[i-1][j+1] + graph[i-1][j+2]

def shape6(i, j): # L대칭 시계방향 회전
    if i+1 >= n or j+2 >=m:
        return 0
    return graph[i][j] + graph[i+1][j] + graph[i+1][j+1] + graph[i+1][j+2]

def shape7(i, j): # L 시계방향 회전x2
    if i+2 >= n or j+1 >= m:
        return 0
    return graph[i][j] + graph[i][j+1] + graph[i+1][j+1] + graph[i+2][j+1]

def shape8(i, j): # L대칭 시계방향 회전x2
    if i+2 >= n or j+1 >= m:
        return 0
    return graph[i][j] + graph[i][j+1] + graph[i+1][j] + graph[i+2][j]

def shape9(i, j): # L 시계방향 회전x3
    if i-1 < 0 or j+2 >= m:
        return 0
    return graph[i][j] + graph[i][j+1] + graph[i][j+2] + graph[i-1][j+2]

def shape10(i, j): # L대칭 시계방향 회전x3
    if i+1 >= n or j+2 >= m:
        return 0
    return graph[i][j] + graph[i][j+1] + graph[i][j+2] + graph[i+1][j+2]

def shape11(i, j): # ㅁ모양
    if i+1 >= n or j+1 >= m:
        return 0
    return graph[i][j] + graph[i][j+1] + graph[i+1][j] + graph[i+1][j+1]

def shape12(i, j): # 번개모양
    if i+2 >= n or j+1 >= m:
        return 0
    return graph[i][j] + graph[i+1][j] + graph[i+1][j+1] + graph[i+2][j+1]

def shape13(i, j): # 번개모양 회전
    if i-1 < 0 or j+2 >= m:
        return 0
    return graph[i][j] + graph[i][j+1] + graph[i-1][j+1] + graph[i-1][j+2]

def shape14(i, j): #번개모양 대칭
    if i+2 >= n or j-1 < 0:
        return 0
    return graph[i][j] + graph[i+1][j] + graph[i+1][j-1] + graph[i+2][j-1]

def shape15(i, j): #번개모양 대칭 회전
    if i+1 >= n or j+2 >= m:
        return 0
    return graph[i][j] + graph[i][j+1] + graph[i+1][j+1] + graph[i+1][j+2]

def shape16(i, j): #ㅗ모양
    if i-1 < 0 or j+2 >= m:
        return 0
    return graph[i][j] + graph[i][j+1] + graph[i-1][j+1] + graph[i][j+2]

def shape17(i, j): #ㅗ모양 회전
    if i+2 >= n or j+1 >= m:
        return 0
    return graph[i][j] + graph[i+1][j] + graph[i+1][j+1] + graph[i+2][j]

def shape18(i, j): #ㅗ모양 회전x2
    if i+1 >= n or j+2 >= m:
        return 0
    return graph[i][j] + graph[i][j+1] + graph[i+1][j+1] + graph[i][j+2]

def shape19(i, j): #ㅗ모양 회전x3
    if i+2 >= n or j-1 < 0:
        return 0
    return graph[i][j] + graph[i+1][j] + graph[i+1][j-1] + graph[i+2][j]


for i in range(n):
    graph.append(list(map(int,input().split())))

for i in range(n):
    for j in range(m):
        ans = max(ans, shape1(i,j), shape2(i,j), shape3(i,j), shape4(i,j), shape5(i,j), shape6(i,j), shape7(i,j), shape8(i,j), shape9(i,j),
                  shape10(i,j), shape11(i,j), shape12(i,j), shape13(i,j), shape14(i,j), shape15(i,j), shape16(i,j), shape17(i,j), shape18(i,j), shape19(i,j))

print(ans)

 

 

 

 

https://github.com/HongEunho

 

HongEunho - Overview

📖 Android, Java, Kotlin, Algorithm. HongEunho has 15 repositories available. Follow their code on GitHub.

github.com

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

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

반응형
반응형

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

 

8911번: 거북이

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 컨트롤 프로그램이 주어진다. 프로그램은 항상 문제의 설명에 나와있는 네가지 명령으로만 이루어져

www.acmicpc.net

거북이 로봇이 좌표 ( 0, 0 ) 을 시작으로 움직인다. 알파벳으로 명령을 하게 되는데,

  • F: 한 눈금 앞으로
  • B: 한 눈금 뒤로
  • L: 왼쪽으로 90도 회전
  • R: 오른쪽으로 90도 회전 이다.

주의할 점은, L과 R 명령일 때는 움직이지 않고 현재 내 좌표에서 방향만 바꾸는 것이다.

 

각각의 케이스에 대하여, 거북이의 이동좌표를 모두 포함하는 가장 작은 직사각형의 넓이를 출력하면 된다.

즉, (0,0) -> (0,1) -> (0,2) -> (1,2) 로 이동하였다면 정답은 2가 되는 것이다.

 

이 문제는 문제를 보며 해결 과정을 하나씩 발견해가며 그 과정을 소스코드로 바꾸는 '구현(Implementation)' 유형이다.

 

코드는 다음과 같다.

n = int(input())

dx = [0,-1,0,1]
dy = [1,0,-1,0] # 북 서 남 동

for i in range(n):
    pos_x = 0
    pos_y = 0
    pos_dir = 0  # 0북 1서 2남 3동
    move = list(input())
    trace = [(pos_x, pos_y)]
    for j in move:
        if j == 'F':
            pos_x = pos_x + dx[pos_dir]
            pos_y = pos_y + dy[pos_dir]
        elif j == 'B':
            pos_x = pos_x - dx[pos_dir]
            pos_y = pos_y - dy[pos_dir]
        elif j == 'L':
            if pos_dir == 3:
                pos_dir = 0
            else:
                pos_dir += 1
        elif j == 'R':
            if pos_dir == 0:
                pos_dir = 3
            else:
                pos_dir -= 1

        trace.append((pos_x, pos_y))
    width = max(trace, key = lambda x:x[0])[0] - min(trace, key = lambda x:x[0])[0]
    height = max(trace, key = lambda x:x[1])[1] - min(trace, key = lambda x:x[1])[1]
    print(width * height)


궁금한 점이 있으면 언제든지 댓글 남겨주세요

 

https://github.com/HongEunho

 

HongEunho - Overview

📖 Android, Java, Kotlin, Algorithm. HongEunho has 15 repositories available. Follow their code on GitHub.

github.com

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

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

반응형
반응형

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

 

1654번: 랜선 자르기

첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그

www.acmicpc.net

문제는 내가 현재 가지고 있는 서로 다른 길이의 랜선들을 잘라서 동일한 길이의 새로운 랜선을 여러개 만드는 것이다.

내가 가지고 있는 랜선의 개수 K와 새로 만들 랜선의 개수 N을 입력받는다.

예를 들어 K=4, N=11 이라면 4개의 긴 랜선을 잘라 11개의 짧은 랜선을 만드는 것이다.

이 때, 11개를 만들 수 있는 랜선의 최대 길이를 구하면 된다.

즉, 11개를 만들기 위해서 랜선을 얼마나 잘라야 하는지를 알면 된다.

 

정답으로 200을 출력한다면 가지고 있는 4개의 랜선으로 새로운 랜선 11개 만들 때 이 새로운 랜선의 최댓값이 200이 된다는 말이다.

 

문제에서 주어진 랜선의 길이는 2^31 - 1보다 작거나 같은 자연수 이기 때문에 절대 앞에서 부터 하나씩 값을 검사하는 순차탐색으로는 시간내에 해결할 수 없다.

 

그래서 이진탐색(Binary Search)을 이용하였다.

내가 가지고 있는 랜선의 길이의 합을 end값으로, 0을 start값으로 설정하여 이 두 값의 절반을 mid값으로 설정한 후, 탐색을 하면 된다. 0과 1600이라면 800부터 검사를 시작하여 문제를 해결해 나가면 된다.

 

순차탐색보다 훨씬 시간도 줄어들고, 시간 초과 문제도 해결할 수 있다.

 

코드는 다음과 같다.

k, n = map(int, input().split())
lan = []

maxcm = 0


def binary_search(array, target, start, end):
    while start <= end:
        moksum = 0
        mid = (start + end) // 2
        if mid == 0:
            return start        # 0값을 나누는 예외상황 처리
        for i in array:
            mok = i // mid
            moksum += mok
        if moksum < target:  # 개수를 더 늘려야 하므로 길이를 줄이자
            end = mid - 1
        elif moksum >= target:  # 개수를 더 줄일 수 있으므로 길이를 늘리자
            start = mid + 1

    return end


for i in range(k):
    lan.append(int(input()))

lansum = sum(lan)  # 입력받은 모든 랜선 길이의 합


result = binary_search(lan, n, 0, lansum) # 길이 배열, 만들어야 하는 랜선수, 시작값, 끝값
print(result)

 

https://github.com/HongEunho

 

HongEunho - Overview

📖 Android, Java, Kotlin, Algorithm. HongEunho has 15 repositories available. Follow their code on GitHub.

github.com

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

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

반응형
반응형

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

 

3020번: 개똥벌레

개똥벌레 한 마리가 장애물(석순과 종유석)로 가득찬 동굴에 들어갔다. 동굴의 길이는 N미터이고, 높이는 H미터이다. (N은 짝수) 첫 번째 장애물은 항상 석순이고, 그 다음에는 종유석과 석순이

www.acmicpc.net

지난번에 이분탐색(Binary Search)으로 풀었던 개똥벌레 문제

https://hongcoding.tistory.com/5

 

[백준] 3020번 개똥벌레 (Python 파이썬)

https://www.acmicpc.net/problem/3020 3020번: 개똥벌레 개똥벌레 한 마리가 장애물(석순과 종유석)로 가득찬 동굴에 들어갔다. 동굴의 길이는 N미터이고, 높이는 H미터이다. (N은 짝수) 첫 번째 장애물은 항

hongcoding.tistory.com

이 문제를 누적합 (전위합(Prefix Sum)) 으로 다시 풀었다.

높이 h부터 높이 1까지 누적 합을 계산하면 높이 i의 배열 값은 높이 i 이상의 모든 석순의 개수가 된다.

예를 들어, 높이가 6인 동굴에서 높이 5의 개똥벌레가 날아갈 때, 높이 5 이상의 석순에 모두 부딪히기 때문에

배열 5의 값이 높이 5의 개똥벌레가 부딪히는 석순의 개수가 된다.

 

마찬가지로 종유석은 위에서부터 내려오기 때문에 h - i + 1의 식을 이용하면 된다.

왜냐하면, 높이 6의 동굴에서 높이 2짜리 종유석은 높이 4 (실질적으로 3.5) 위로의 개똥벌레가 모두 부딪히기 때문이다.

즉, 석순처럼 높이2라고 해서 높이 2 밑의 개똥벌레가 부딪히는것이 아니라 위에서 부터기 때문에 반대가 된다.

 

파이썬 코드는 다음과 같다.

n, h = map(int, input().split())

down = [0] * (h + 1)  # 석순
up = [0] * (h + 1)  # 종유석

min_count = n  # 파괴해야 하는 장애물의 최소값
range_count = 0  # 최소값이 나타나는 구간의 수

for i in range(n):
    if i % 2 == 0:
        down[int(input())] += 1
    else:
        up[int(input())] += 1

for i in range(h - 1, 0, -1):
    down[i] += down[i + 1]
    up[i] += up[i + 1]

for i in range(1, h + 1):

    if min_count > (down[i] + up[h - i + 1]):
        min_count = (down[i] + up[h - i + 1])
        range_count = 1
    elif min_count == (down[i] + up[h - i + 1]):
        range_count += 1

print(min_count, range_count)

모르시는 부분이 있으시면 언제든지 댓글 남겨주세요!

 

https://github.com/HongEunho

 

HongEunho - Overview

📖 Android, Java, Kotlin, Algorithm. HongEunho has 15 repositories available. Follow their code on GitHub.

github.com

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

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

반응형
반응형

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

 

3020번: 개똥벌레

개똥벌레 한 마리가 장애물(석순과 종유석)로 가득찬 동굴에 들어갔다. 동굴의 길이는 N미터이고, 높이는 H미터이다. (N은 짝수) 첫 번째 장애물은 항상 석순이고, 그 다음에는 종유석과 석순이

www.acmicpc.net

문제에 대한 자세한 설명은 위 링크에 기술 되어있다.

쉽게 풀어쓰자면 동굴의 길이(N)와 높이(H)를 입력받는다.

동굴은 석순과 종유석으로 구성되어 있는데, 석순은 아래에서 자라는 고드름 종유석은 천장에서 나는 고드름이라고 생각하면 된다. 

문제에서 동굴의 길이만큼 석순과 종유석의 길이를 입력받는데, 번갈아 가면서 입력받는다. ( 석순과 종유석은 각각 동굴의 길이 1만큼 차지한다)

예를 들어, 1 3 4 2 5 6 이라고 입력했으면 석순 1, 4, 5 / 종유석 3 2 6 이 되는 것이다.

이렇게 장애물이 설치된 동굴에 개똥벌레 한마리가 날라가는데 동굴의 높이가 6일 때, 개똥벌레가 날아가는 높이가 3이라고 한다면 아래에서부터 높이 2~3 (2.5라고 생각하면 쉽다) 구간을 날라간다. 

그래서 3보다 낮은 석순에는 모두 부딪히게 되고, 3보다 큰 종유석에는 모두 부딪히게 된다. ( 위에서 부터 4 만큼 내려온 종유석에는 아래에서 부터 2.5만큼 날아오른 개똥벌레가 부딪히기 때문)

 

이런 상황에서 문제에서 최종적으로 구하고자 하는 것은, 개똥벌레가 파괴해야 하는 장애물의 최소 개수와 이 최소값이 나오는 구간의 수를 구하는 것이다.

 

그렇다면 어떻게 접근해야 할까?

가장 먼저 떠오른 방법은 석순과 종유석의 배열을 따로 두고, 각각의 배열을 정렬 한 후에 처음 개똥벌레가 부딪히기 시작한 높이를 계산하는 방식이다. 왜냐하면 그 이후의 구간은 모두 부딪힌다는 이야기가 되기 때문에 첫 구간만을 구해 그 구간 전까지의 개수를 통해 답을 구할 수 있기 때문이다. 이러한 접근 방식을 누적 합(또는 구간합)이라고 하는데

현재 페이지에서는 다른 방식으로 풀어보려고 한다.

 

바로 이진탐색(Binary Search) 방식으로 풀려고 한다.

석순과 종유석의 배열이 각각 정렬되어 있기 때문에, 배열의 중간지점에서 개똥벌레가 부딪히는지 테스트를 진행한다.

보통의 이진탐색 과정과 마찬가지로 start값과 end값에 변화를 주며 mid값을 조정하여 개똥벌레가 최소한으로 부딪히는 구간을 찾으면 된다.

 

코드는 다음과 같다.

n, h = map(int, input().split())

down = []
up = []
for i in range(n):
    if i % 2 == 0:
        down.append(int(input()))
    else:
        up.append(int(input()))

down.sort()
up.sort()

min_count = n
range_count = 0


def binary_search(array, target, start, end):
    while start <= end:
        mid = (start + end) // 2

        if array[mid] < target:
            start = mid + 1
        else:
            end = mid - 1

    return start


for i in range(1, h + 1):
    down_count = len(down) - binary_search(down, i - 0.5, 0, len(down) - 1)
    top_count = len(up) - binary_search(up, h - i + 0.5, 0, len(up) - 1)

    if min_count == down_count + top_count:
        range_count += 1
    elif min_count > down_count + top_count: # 현재 범위가 새로운 최소 값이면
        range_count = 1
        min_count = down_count + top_count

print(min_count, range_count)

binary_search함수의 target은 개똥벌레의 높이가 되며 down일 때는 i - 0.5, up일때는 h - i + 0.5를 넣는다.

위에서 자라는 종유석의 경우에는 아래와는 반대로 생각해야 하기 때문이다.

 

https://github.com/HongEunho

 

HongEunho - Overview

📖 Android, Java, Kotlin, Algorithm. HongEunho has 15 repositories available. Follow their code on GitHub.

github.com

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

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

반응형
반응형

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

 

10815번: 숫자 카드

첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10,

www.acmicpc.net

이 문제는 내가 입력한 숫자들이 상근이가 가지고 있는 숫자들에 존재하는지 확인하는 문제이다.

 

변수 n은 상근이의 숫자 카드 개수, card 는 그 카드들의 숫자 목록이다.

m은 내 카드 개수, check는 내 카드들의 숫자 목록이다.

즉 check의 요소들이 card에 존재 하는가를 검사 하면 된다.

 

이렇게 요소들을 확인하는 문제는 이진탐색(Binary Search) 문제라고 생각하면 쉽다.

요소가 엄청 작은 문제가 아닌 이상, 순차 탐색은 시간초과가 나오기 때문에 이분 탐색을 이용하자.

 

코드는 다음과 같다.

import sys

n = int(input())
card = list(map(int, sys.stdin.readline().split()))
m = int(input())
check = list(map(int, sys.stdin.readline().split()))

card.sort()

def binary_search(array, target, start, end):
    while start <= end:
        mid = (start + end) // 2

        if array[mid] == target:
            return mid
        elif array[mid] > target:
            end = mid - 1
        else:
            start = mid + 1
    return None


for i in range(m):
    if binary_search(card, check[i], 0, n - 1) is not None:
        print(1, end=' ')
    else:
        print(0, end=' ')

 

https://github.com/HongEunho

 

HongEunho - Overview

📖 Android, Java, Kotlin, Algorithm. HongEunho has 15 repositories available. Follow their code on GitHub.

github.com

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

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

 

반응형
반응형

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

 

2110번: 공유기 설치

첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가

www.acmicpc.net

문제에서 주어진 대로, N개의 집에 C개의 공유기를 설치한다.

이 때, 가장 인접한 두 공유기 사이의 거리가 최대 가 되도록 해야 한다.

 

즉, 집의 좌표가 [ 1, 2, 4, 8, 9 ] 이고 공유기를 3개 설치 할 때, 공유기를 1, 4, 8 혹은 1, 4, 9 에 설치를 해야

가장 인접한 두 공유기 사이의 거리(1, 4)가 3이 되고, 이 3 보다 작게 설치를 할 수는 없다.

 

그렇다면, 공유기를 설치해야 될 집은 어떻게 찾아야 할까?

가장 간단한 방법으로는 순차 탐색으로 앞에서 부터 일일이 설치 집을 탐색해보며 실행하는 방법이 있지만,

가장 비효율적인 방법이며 분명 시간 제한 오류가 난다.

이러한 탐색 문제를 가장 빠르게 푸는 방법은 바로 이진 탐색(Binary Search) 이다.


이진 탐색을 쉽게 설명하자면,

예를들어, 1 부터 100까지의 숫자 사이에서 랜덤으로 정해진 숫자 하나를 맞추는 게임을 한다고 하자.

이 때 내가 부를 수 있는 숫자의 횟수는 3회이며, 숫자를 외칠 때 마다 정답이 그 숫자보다 작은지 큰지 맞는지 확인할 수 있다. 랜덤으로 정해진 숫자는 80이고, 나는 이 정답을 모르는 상태라고 가정하자.

 

처음엔 당연히 절반인 50을 부르는게 좋을 것이다. 이 때 정답이 50보다 크기 때문에 출제자는 50보다 크다고 알려 줄 것이며 그 다음에는 50보다 작은 부분은 검사할 필요가 없다. 그래서 그 다음엔 50과 100의 절반인 75를 부른다.

만약 75보다도 크다면 또 75보다 작은 부분은 검사할 필요가 없다.

이런 식으로 절반 씩 쪼개가며 탐색할 부분을 좁혀가는 방법이다.

 

만약 순차 탐색으로 진행했다면 1부터 80까지 80번을 실행해야 하지만, 이진 탐색을 실행하면 불과 5회 정도 만에 답을 찾아낼 수 있는 것이다.


이 방법으로 문제를 진행해보면

1. array라는 리스트에 집들의 좌표를 입력받은 후에 정렬.

2. start = 1, end = array[-1] - array[0] 으로 설정. ( 시작값은 최소 거리, 끝 값은 최대 거리 )

3. 앞 집부터 공유기 설치

4. 설치할 수 있는 공유기 개수가 c개를 넘어가면 더 넓게 설치할 수 있다는 이야기 이므로 설치거리를 mid + 1로 설정하여 다시 앞집부터 설치.

5. c개를 넘어가지 않는다면 더 좁게 설치해야 한다는 이야기 이므로 mid - 1로 설정.

 

위의 과정을 반복실행하면 정답을 얻을 수 있다.

코드는 다음과 같다.

n, c = map(int, input().split())

array = []
for i in range(n):
    array.append(int(input()))

array.sort()


def binary_search(array, start, end):
    while start <= end:
        mid = (start + end) // 2
        current = array[0]
        count = 1

        for i in range(1, len(array)):
            if array[i] >= current + mid:
                count += 1
                current = array[i]

        if count >= c:
            global answer
            start = mid + 1
            answer = mid
        else:
            end = mid - 1


start = 1
end = array[-1] - array[0]
answer = 0

binary_search(array, start, end)
print(answer)

 

https://github.com/HongEunho

 

HongEunho - Overview

📖 Android, Java, Kotlin, Algorithm. HongEunho has 15 repositories available. Follow their code on GitHub.

github.com

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

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

반응형
반응형

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

 

11559번: Puyo Puyo

총 12개의 줄에 필드의 정보가 주어지며, 각 줄에는 6개의 문자가 있다. 이때 .은 빈공간이고 .이 아닌것은 각각의 색깔의 뿌요를 나타낸다. R은 빨강, G는 초록, B는 파랑, P는 보라, Y는 노랑이다.

www.acmicpc.net

어렸을 때 해봤던 '뿌요뿌요' 게임을 구현한다고 생각하면 될 것 같다.

 

코드의 풀이 방식은 다음과 같다.

 

1. 맵(graph)을 돌면서 '.'이 아닌 것(뿌요)을 발견하면 BFS를 실행한다.

2. BFS로 진입하여 현재 터뜨릴 수 있는 뿌요를 모두 터뜨려 준다.

3. 뿌요가 터졌기 때문에 맵을 한번 정리해준다(gravity)

4. 터뜨릴 수 있는 뿌요가 계속 남아있을 때 까지 위 과정을 반복한다.

 

다만 주의 할 점은!

문제에도 명시되어 있지만 동시에 두 종류 이상의 뿌요가 터져도 한번의 연쇄만 추가 해야 한다는 것이다.

해당 설명은 코드 아래에도 다시 명시해 놓았다.

from collections import deque

graph = []

dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]

result = 0


def bfs(a, b, c):
    queue = deque()
    queue.append((a, b))

    pang = deque()
    pang.append((a, b))

    visited = [[False] * 6 for _ in range(12)]
    visited[a][b] = True
    count = 1
    flag = 0

    while queue:
        x, y = queue.popleft()

        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if nx < 0 or nx > 11 or ny < 0 or ny > 5:
                continue
            if graph[nx][ny] == c and not visited[nx][ny]:
                queue.append((nx, ny))
                pang.append((nx, ny))
                visited[nx][ny] = True
                count += 1

    if count >= 4:
        flag = 1

        for x, y in pang:
            graph[x][y] = "."

    return flag


def gravity():
    for y in range(6):
        queue = deque()
        for x in range(11, -1, -1):
            if graph[x][y] != '.':
                queue.append(graph[x][y])
        for x in range(11, -1, -1):
            if queue:
                graph[x][y] = queue.popleft()
            else:
                graph[x][y] = '.'


for i in range(12):
    graph.append(list(input()))


while True:
    chk = 0
    for i in range(12):
        for j in range(6):
            if graph[i][j] != '.':
                chk += bfs(i, j, graph[i][j])

    if chk == 0:
        print(result)
        break
    else:
        result += 1
    gravity()

# 처음에는 result를 bfs함수 안에서 global 변수로 선언하여
# 팡이 될 때 마다 +1을 해주는 방식으로 하였는데
# 이렇게 해주면, 동시에 두 뿌요가 터지는 경우에도 두 개를 카운트를 해 준다.
# 하지만 문제에서, 동시에 여러개의 뿌요가 터질 때는 한 번 카운트를 해주라고 명시했기 때문에
# bfs 함수 안이 아닌, 바깥에서 +1을 해주는 방식으로 변경하였다. 이렇게 하니 정답이 나온다.

 

https://github.com/HongEunho

 

HongEunho - Overview

📖 Android, Java, Kotlin, Algorithm. HongEunho has 15 repositories available. Follow their code on GitHub.

github.com

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

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

반응형

+ Recent posts