알고리즘 문제 풀이

지금까지 배운 것들을 응용해서 문제를 푸는 연습을 해보자!

• 버스 노선 문제

(예시 코드 - 미완성, 참고만 하기!)

T = int(input())
for tc in range(T):
    N = int(input())    # 버스 노선 개수
    counts = [0] * 5001 # N개의 5000번 정류장 개수
    for _ in range(N):  # 버스 노선 입력
        A, B = map(int, input().split())
        for j in range(A, B+1):
            counts[j] += 1
    P = int(input())    # 버스 정류장 개수
    bus_stop = [int(input()) for _ in]

    for _ in range(P):  # 버스 정류장 입력 (리스트의 원소)
        c = int(input())
        bus_stop.append(c)
    result = []
    for b in bus_stop:
        result.append(bus_check(bus_route, b))

    print(f'#{tc+1}',end=' ')
    print(*result)

 

• 어디에 단어가 들어갈 수 있을까

# 가로 또는 세로로 연속한 1의 개수가 k인 경우를 센다.
T = int(input())
for tc in range(1, T+1):
    N, K = map(int, input().split())
    arr = [list(map(int, input().split())) + [0] for _ in range(N)] + [[0] * (N+1)]
    N += 1  # 0인 열과 행을 추가
    ans = 0
    for i in range(N):
        count = 0   # i 행에서 연속한 1의 개수
        for j in range(N):
            if arr[i][j]:
                count += 1
            else:
                if count == K:
                    ans += 1
                count = 0

    for j in range(N):
        count = 0   # j 열에서 연속한 1의 개수
        for i in range(N):
            if arr[i][j]:
                count += 1
            else:
                if count == K:
                    ans += 1
                count = 0
    print((f'#{tc} {ans}'))

퍼즐 안에 딱 k 만큼 공간이 있을 때만 카운트가 되고 k 초과인 공간은 카운트 하지 않는 것을 구현하는 것에서 어려움을 느꼈다.

값이 1인 공간을 만날 때마다 카운트를 쌓다가 0을 만나거나 끝자리에 도달하면 카운트를 검사하여 k와 값이 같을 때만 카운트를 반영하는 방법을 새롭게 알 수 있었다.

• • 풍선팡 2

T = int(input())
for tc in range(T):
    N, M = map(int, input().split())    # N = 행 개수 , M = 풍선 개수 = 열 개수
    arr = [list(map(int, input().split())) for _ in range(N)]
    dr = [0, 1, 0, -1]  # 우 하 좌 상
    dc = [1, 0, -1, 0]
    flower_spread = []
    for r in range(N):
        for c in range(M):
            sum = arr[r][c]
            for i in range(4):
                nr = r + dr[i]
                nc = c + dc[i]
                if 0 <= nr <= N-1 and 0 <= nc <= M-1:
                    sum += arr[nr][nc]
            flower_spread.append(sum)
    result = max(flower_spread)
    print(f'#{tc+1} {result}')

 

• 풍선팡

T = int(input())
for tc in range(T):
    N, M = map(int, input().split())    # N = 행 개수 , M = 풍선 개수 = 열 개수
    arr = [list(map(int, input().split())) for _ in range(N)]
    dr = [0, 1, 0, -1]  # 우 하 좌 상
    dc = [1, 0, -1, 0]
    flower_spread = []
    for r in range(N):
        for c in range(M):
            sum = arr[r][c]
            for i in range(4):
                for s in range(1, arr[r][c] + 1):
                    nr = r + dr[i] * s
                    nc = c + dc[i] * s
                    if 0 <= nr <= N-1 and 0 <= nc <= M-1:
                        sum += arr[nr][nc]
            flower_spread.append(sum)
    result = max(flower_spread)
    print(f'#{tc+1} {result}')