알고리즘

뚝딱뚝딱·2024년 3월 16일

SWEA

상호의 배틀필드(1873)

배틀필드

import sys
# sys.stdin = open('input.txt')

T = int(input())

for tc in range(1, T + 1):
    H, W = map(int, input().split())
    MAP = [list(input()) for _ in range(H)]
    N = int(input())
    comm = input()

    for i in range(H):
        for j in range(W):
            if MAP[i][j] in '<>^v':
                row = i
                col = j
                break

    for i in range(len(comm)):
        t_row = row
        t_col = col

        if comm[i] == 'U':
            MAP[t_row][t_col] = '^'
            if t_row-1 >= 0 and MAP[t_row-1][t_col] == '.':
                MAP[t_row-1][t_col] = '^'
                MAP[t_row][t_col] = '.'
                row -= 1

        elif comm[i] == 'R':
            MAP[t_row][t_col] = '>'
            if t_col+1 < W and MAP[t_row][t_col+1] == '.':
                MAP[t_row][t_col+1] = '>'
                MAP[t_row][t_col] = '.'
                col += 1

        elif comm[i] == 'L':
            MAP[t_row][t_col] = '<'
            if t_col -1 >= 0 and MAP[t_row][t_col-1] == '.':
                MAP[t_row][t_col-1] = '<'
                MAP[t_row][t_col] = '.'
                col -= 1

        elif comm[i] == 'D':
            MAP[t_row][t_col] = 'v'
            if t_row+1 < H and MAP[t_row+1][t_col] == '.':
                MAP[t_row+1][t_col] = 'v'
                MAP[t_row][t_col] = '.'
                row += 1

        elif comm[i] == 'S':
            if MAP[t_row][t_col] == '^':
                if t_row -1 >= 0:
                    for u in range(t_row-1, -1, -1):
                        if MAP[u][t_col] == '*':
                            MAP[u][t_col] = '.'
                            break
                        elif MAP[u][t_col] == '#':
                            break

            elif MAP[t_row][t_col] == '>':
                if t_col + 1 < W:
                    for r in range(t_col + 1, W):
                        if MAP[t_row][r] == '*':
                            MAP[t_row][r] = '.'
                            break
                        elif MAP[t_row][r] == '#':
                            break

            elif MAP[t_row][t_col] == 'v':
                if t_row + 1 < H:
                    for d in range(t_row +1, H):
                        if MAP[d][t_col] == '*':
                            MAP[d][t_col] = '.'
                            break
                        elif MAP[d][t_col] == '#':
                            break

            elif MAP[t_row][t_col] == '<':
                if t_col - 1 >= 0:
                    for l in range(t_col - 1, -1, -1):
                        if MAP[t_row][l] == '*':
                            MAP[t_row][l] = '.'
                            break
                        elif MAP[t_row][l] == '#':
                            break

    print(f'#{tc} {"".join(MAP[0])}')
    for k in range(1, H):
        print("".join(MAP[k]))

문제 제목 붙이기(7087) ⇒ 파이썬 제출 안됨

sol

T = int(input())

for tc in range(1, T+1):
    cnt = 0
    N = int(input())
    ls = []
    for _ in range(N):
        ls.append(input())
        ls.sort()
        # print(ls)
        log = 0
        for i in range(len(ls)-1):
            if log == 0:
                if ord(ls[i][0]) == ord(ls[i+1][0]):
                    cnt += 1
                    log = 1
                if ord(ls[i][0]) + 1 == ord(ls[i+1][0]):
                    cnt += 1
                else:
                    break
            else:
                if ord(ls[i][0]) + 1 == ord(ls[i+1][0]):
                    cnt += 1
                else:
                    break

    print(f'#{tc} {cnt}')

영준이의 카드 카운팅(4047)
퍼팩트 셔플(3499)
패턴 마디의 길이(2007)

sol

T = int(input())
cnt = 0 # 마디의 길이를 출력할거다

for tc in range(1, T+1):
    sentence = list(input())
    # print(sentence)
    # N = len(sentence)
    madi = 0
    for i in range(1, 11):
        if sentence[:i] == sentence[i:i*2]:
            madi = i
            break
    print(f'#{tc} {madi}')

간단한 369게임(1926)
자기방으로 돌아가기(4408)

자기방

'''
겹치는 만큼 기다려야하니까 가장 많이 겹치는 만큼이 최소 걸리는 시간이 되겠다!!
'''

T = int(input())
for tc in range(1, T+1):
    N = int(input())  # 학생 수
    arr = [list(map(int, input().split())) for _ in range(N)]

    # for _ in range(N):
    #     go, to = map(int, input().split()) 9# 현재 방과 돌아갈 방
    #     print(go,to)
    # print(arr)

    cnt = [0] * 201         # 방사이 공간을 지나는 사람수를 기록할 복도
    for a, b in arr:        # arr에서 두개 꺼낼건데 a <= b라는 보장이 없음에 주의!!
                            # 복도번호 = (방번호 + 방번호%2) // 2
        a = (a + a % 2)//2
        b = (b + b % 2)//2
        for i in range(min(a, b), max(a, b)+1):  # 둘 중 작은데서 출발해서 둘중 큰곳으로 도착
            cnt[i] += 1
    print(f'#{tc} {max(cnt)}')

재밌는 오셀로 게임
18575

sol

T = int(input())

di = [-1,0,1,0]
dj = [0,1,0,-1]

for tc in range(1, T +1):
    N = int(input())
    arr = [list(map(int, input().split())) for _ in range(N)]

    max_sum = 0
    min_sum = 987654321
    for i in range(N):
        for j in range(N):
            point = arr[i][j]
            for k in range(4):
                for l in range(1, N):
                    ni = i + di[k]*l
                    nj = j + dj[k]*l
                    if 0 <= ni < N and 0 <= nj < N:
                        point += arr[ni][nj]

            if max_sum <= point:
                max_sum = point
            if min_sum >= point:
                min_sum = point
    result = max_sum - min_sum
    print(f'#{tc} {result}')

당근 포장하기(16811)

sol

def check(N, ls): # 당근의 크기를 입력하면 모든 조건을 확인하는 프로그램
    '''
    당근 3개 => 소,중,대 상자에 든 당근의 개수 차이 = 0 소 1 중 1 대 1 씩 들어갔으니까
    당근 5개  > 소 3 중 1 대 1 = 당근의 개수 차이 2
        그런데 2개 초과하는 상자 잇으니까 조건 만족 x
    당근 8개
    '''
    L = int(N/2) # L초과하는 당근이 있으면 안됨
    ls.sort()
    min_chai = 987654321  # 포장개수차이 최소값 초기값 설정
    for i in range(N-2):
        for j in range(i+1, N-1):
            if ls[i] != ls[i+1] and ls[j] != ls[j+1]:
                small = i+1
                middle = j-i
                large = N-1-j
                if small <= L and middle <= L and large <= L:
                    if min_chai >= (max(small, middle, large) - min(small, middle, large)):
                        min_chai = max(small, middle, large) - min(small, middle, large)
    return min_chai

T = int(input()) # 수확횟수
for tc in range(1, T+1):
    N = int(input()) # 수확한 당근의 개수 3
    C = list(map(int, input().split())) # 당근의 크기 1 2 3
    # C.sort() # 당근을 크기 순으로 정렬
    # min_v = 1000 # 포장별 최소 개수 차이, 포장 불가인 경우 -1
    # for i in range(N-2):
    #     for j in range(i+1, N-1):
    #         if C[i] != C[i+1] and C[j] != C[j+1]: # 같은 크기 사이에 경계를 두면 안돼
    #             small = i + 1   # 소 상자에 들어간 당근 개수
    #             middle = j-i    # 중 상자에 들어간 당근 개수
    #             large = N-1-j   # 대 상자에 들어간 당근 개수
    #             if 0 < small <= N//2 and 0 < middle <= N//2 and 0 < large <= N//2:
    #                 if min_v > (max(small, middle, large) - min(small, middle, large)):
    #                     min_v = max(small, middle, large) - min(small, middle, large)
    res = check(N,C)
    if res == 987654321:
        print(f'#{tc} -1')
    else:
        print(f'#{tc} {res}')

백준

스위치켜고끄기
주사위_쌓기
창고_다각형
일곱_난쟁이(2309)

난쟁이

K = 100
S = 0
ls = []
for i in range(9):
    ls.append(int(input()))

S = sum(ls)
find = S - K
ls.sort()
a = 0
b = 0

N = len(ls)
for j in range(N-1):
    for k in range(j+1, N):
        if ls[j] + ls[k] == find:
            a = ls[j]
            b = ls[k]
            # print(a, b) = 15, 25
            # print(type(a)) -> int

for f in ls:
    if f != a and f != b:
        print(f)

참외밭
직사각형
2527
직사각형을 만드는 방법

8320

N = int(input())

# [1] 가능한 경우를 모두 순회
ans = 0
for i in range(1, N+1):
    for j in range(i, N+1):
        if i*j <= N:
            ans += 1
print(ans)

# [2] 몫 연산을 통해서 처리
ans = N
for i in range(2, N):
    n = N // i - (i-1)
    if n < 1:
        break
    ans += n
print(ans)

수열

2559

# N = 온도측정한 전체 날짜의 수, K = 합구하기 위한 연속적인 날짜의 수
N, K = map(int, input().split())
degrees = list(map(int, input().split())) # 매일 측정한 온도
result = [] # 온도의 합을 구해서 넣어둘 리스트
result.append(sum(degrees[0:K])) # 0번째부터 K-1번째까지 먼저 합해서 넣어준다음
for i in range(N-K): # K개만큼 더해야하니까 인덱스 번호 N에서 K 빼준 범위로 설정
   result.append(result[i]-degrees[i]+degrees[i+K])
   # 더한거에서 젤 앞에꺼 빼고 그다음 하나 더해주기(한칸씩 뒤로 가는겨)
print(max(result)) # 리스트에 넣어둔 것들 중 가장 큰값 프린트 하기

색종이(2563)

색종이

N = int(input())

matrix = [[0]*102 for _ in range(102)] # 색종이 표시할 배열

for _ in range(N):
    a, b = map(int, input().split())
    for i in range(a,a+10):
        for j in range(b, b+10):
            matrix[i][j] = 1

result = 0
for k in matrix:
    result += sum(k)  # matrix 안의 k리스트들의 합을 result에 누적시켜 더해주면
                        # 넓이(1로 채워져 있는 곳)이 나온다
print(result)

색종이(10163)

10163

def count(arr):
    cnt = 0
    for ls in arr:
        for k in range(1, len(ls)):
            if ls[k-1] != ls[k]:
                cnt += 1
    return cnt

N = int(input())
tmp = [[0]*102 for _ in range(102)]
for _ in range(N):
    a, b = map(int, input().split())
    for i in range(a, a+10):
        for j in range(b, b+10):
            tmp[i][j] = 1

# tmp2 = list(zip(*tmp))  # 전치행렬 # 튜플형태로 행렬이 전치됨
tmp2 = list(map(list, zip(*tmp)))  # 수정 필요할 시의 전치행렬 # 리스트 형태로 전치됨

result = count(tmp) + count(tmp2)
print(result)

경비원
빙고
줄_세우기

2605

N = int(input()) # 학생의 수
numbers = list(map(int, input().split()))
alst = [n for n in range(1, N+1)]
# print(alst) # [1, 2, 3, 4, 5]

for i in range(N): # i위치의 학생을 순서대로 이동처리
    n, t = numbers[i], alst[i] # 앞으로 이동할 칸 수, 학생번호
    # 순차적으로 덮어씌우기
    # 나한테 전에꺼를 집어넣기
    # 끝난다음에는 alst[i-n]번째에 t 넣어주기
    for j in range(i, i-n, -1):
        alst[j] = alst[j-1]
    alst[i-n] = t
print(*alst)

10431

P = int(input())
for tc in range(1, P+1):
    lst = list(map(int, input().split()))[1:]
    cnt = 0
    for i in range(1, 20):
        for j in range(i): # i의 이전 값들을 비교할것
            if lst[i] < lst[j]: # 더 큰애들이 앞에 서있으면
                cnt += 1 # 카운트 증가

    print(f'{tc} {cnt}')

종이자르기

2628 - idea

'''
가장 큰 종이 조각의 넓이 ?
바깥 둘레에서 잘라야하는 열과 행의 번호를
각각 리스트에 담아서
자르면 나오는 길이가지고
가장 긴 길이 두개 곱하면 가장 큰 색종이 넓이 구할 수 있음 
'''
# 종이의 가로, 세로
W, H = map(int, input().split())
# [1] 가능한 가로/세로 자르는 위치를 저장 후 정렬
w_ls = [0, H]
h_ls = [0, W]
N = int(input()) # 잘라야 하는 점선의 개수

for _ in range(N):
    t, n = map(int, input().split())
    if t == 0:
        w_ls.append(n)
    else:
        h_ls.append(n)
w_ls.sort()
h_ls.sort()
# print(w_ls)
# [2] 가장 긴 길이 찾기
w_mx = 0
for i in range(1, len(w_ls)):
    w_mx = max(w_mx, w_ls[i] - w_ls[i-1])

h_mx = 0
for i in range(1, len(h_ls)):
    h_mx = max(h_mx, h_ls[i] - h_ls[i-1])

print(w_mx*h_mx)

수_이어가기
직사각형네개의합집합의면적구하기

2669

arr = [[0]*102 for _ in range(102)]
for _ in range(4):
    a, b, c, d = map(int, input().split())
    for i in range(b, d):
        for j in range(a, c):
            arr[i][j] = 1
cnt = 0
for k in range(102):
    for l in range(102):
        if arr[k][l] == 1:
            cnt += 1

print(cnt)

자리배정

10157

C, R = map(int, input().split())
K = int(input())

if R*C < K: # 배정이 불가능한 경우 0
    print(0)
else: # 배정하면서 K가 되면 그 때 좌표 출력
    di, dj = [1, 0, -1, 0], [0, 1, 0, -1]
    # 주변을 1로 둘러싸면 : 범위체크 필요없음
    arr = [[1]*(C+2)] + [[1] + [0]*C + [1] for _ in range(R)] + [[1]*(C+2)]

    ci, cj, dr = 1, 1, 0
    for n in range(1, K):
        arr[ci][cj] = n
        ni, nj = ci + di[dr] , cj + dj[dr]
        if arr[ni][nj] == 0: # 비어있으니 이동가능
            ci, cj = ni, nj
        else:   # 범위밖 또는 이미 채워진경우
            dr = (dr+1)% 4
            ci, cj = ci+di[dr], cj+dj[dr]
    print(f'{cj} {ci}')

개미
방_배정

13300

'''
여학생 = 0
남학생 = 1
'''
def count(arr):
    grade = [0] * 7  # 학년 별로 몇명인지 세보자
    # ls = [] #
    for i in arr:   # 성별로 구분해서 학년만 넣어둔 리스트를 순회하면서
        grade[i] += 1 # 그 학년을 인덱스번호로 활용해서 cnt 증가시켜주기
        # print(grade)
    result = 0 # 방 몇개필요한지 구할 결과값변수 초기화
    for k in grade: # 학년별로 몇명인지 누적해서 구해둔 grade리스트 순회하면서
        if k % K == 0:  # 한방에 배정할 수 있는 최대 인원수로 나눈 값이 딱 떨어지면
            result += k//K  # 그 나눗셈 몫만큼의 방을 더해주면 됨
            # print(result)
        else:   # 안나눠 떨어지면 그 안나눠 떨어진 사람을 위해서
            result += k//K + 1  # 방 하나 추가 배정해 주면 됨
    return result # 누적된 방이 몇 개 필요한지에 대한 result값 반환하기

# N = 수학여행에 참가하는 학생 수
# K = 한 방에 배정할 수 있는 최대 인원 수
N, K = map(int, input().split())
cnt_S0 = []
cnt_S1 = []

for _ in range(N):
    S, Y = map(int, input().split())  # 성별 S / 학년 Y
    # print(S, Y)
    if S == 1: # 성별 1일경우
        # cnt_S1.append([S, Y]) # 의 성별과 학년 넣어주기
        cnt_S1.append(Y) # 아니지, 학년만 넣어주자 성별은 노났으니까
    elif S == 0: # 성별 2일경우
        # cnt_S0.append([S, Y])
        cnt_S0.append(Y)

a = count(cnt_S1) # 성별 남자일 경우의 필요 방개수
# print(a)
b = count(cnt_S0)   # 성별 여자일 경우의 필요한 방개수
ans = a+b # 더해서 결과값
print(ans)

'''
print(cnt_S0)
print(cnt_S1)
[1, 2, 2, 3, 6, 5] # 성별 여자인 경우의 학년
[1, 1, 2, 3, 4, 3, 3, 5, 5, 6] # 성별 남자인 경우의 학년'''

딱지놀이

14696

N = int(input())  # 딱지놀이의 총 라운드 수
for _ in range(N):
    A = list(input().split())
    B = list(input().split())
    a_len = int(A[0])
    b_len = int(B[0])
    a_ls = A[1:]
    b_ls = B[1:]

    # 인덱스 이용해서 카운트 해주자(1,2,3,4 입력해주기위해서 *5)
    one_cnt = [0] * 5
    two_cnt = [0] * 5

    for i in range(a_len):
        one_cnt[int(a_ls[i])] += 1
    for j in range(b_len):
        two_cnt[int(b_ls[j])] += 1

    # 4,3,2,1 역순 순회하면서 누가 이기는지 판단하기
    result = ''
    for k in range(4, 0, -1):
        if one_cnt[k] > two_cnt[k]:
            result = 'A'
            break
        elif one_cnt[k] < two_cnt[k]:
            result = 'B'
            break
        else:
            result = 'D'
    print(result)

뚝딱뚝딱

나의 행복 만들기

이전 포스트

State Management

다음 포스트

알고리즘

SWEA

백준

State Management

네트워크_IPv4, ICMP 프로토콜

0개의 댓글