[알고리즘] 구현 - 백준 1009 2563 11655 18111 18405 1092 (그리디)

구현(Implementation)

머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정 - 논리적 사고력이 중요

사실 모든 문제가 구현 문제가 아닐까...?

 

구현 문제풀이

 

백준 1009 분산처리

문제 이해가 좀 헷갈렸다. 시간 초과가 자꾸 떠서... 왜그럴까 생각해보니까 9^635같은 큰 숫자가 들어오면 당연히 시간초과가 날 만 하더라.

 

- 초기 코드

t = int(input())
computer = [0] * t
for i in range(t):
    computer[i] = list(map(int, input().split()))

ans = [0] * t
for i in range(len(computer)):
    tmp = computer[i][0] ** computer[i][1]
    ans[i] = int(str(tmp)[-1])
    
for x in ans:
    print(x)

- 수정 과정

9^635같은 숫자를 직접 계산하도록 두는 것 보다는 제곱될 때마다 반복되는 1의 자리 수를 리스트화 하여 반영하면 될 것 같았다. 그리고 1 <= a < 100인걸 간과했다...

 

- 수정 코드

t = int(input())
num = [1, [2,4,8,6], [3,9,7,1], [4,6], 5, 6, [7,9,3,1], [8,4,2,6], [9,1], 10]

computer = [0] * t
ans = [0] * t

for i in range(t):
    computer[i] = list(map(int, input().split()))


for i in range(len(computer)):
    tmp = computer[i][0] % 10
    if tmp == 1 or tmp == 5 or tmp == 6 or tmp == 0:
        ans[i] = num[tmp - 1]
    elif tmp == 2 or tmp == 3 or tmp == 7 or tmp == 8:
        ans[i] = num[tmp - 1][computer[i][1] % 4 - 1]
    else:
        ans[i] = num[tmp - 1][computer[i][1] % 2 -1]
        
for x in ans:
    print(x)

통과!

 

백준 2563 색종이

 

어떻게든 수학을 사용해서 풀어보려고 했는데... 굳이 그럴 필요 없었다.

배열을 만들어두고 1을 채워서 1의 개수 = 넓이로 구하면 해결된다.

n = int(input())

big = [[0]* 101 for _ in range(101)]

lis = []

for i in range(n):
    x, y = map(int, input().split())
    for k in range(10):
        for m in range(10):
            big[x+k][y+m] = 1
ans = 0
for x in big:
    ans += sum(x)
    
print(ans)

매번 풀때마다 느끼는건데 내가 너무 어렵게 생각하는것 같다...

 

 

백준 11655 ROT13

알파벳을 밀어서 암호를 만드는 문제, 아스키 코드 번호를 사용해서 풀었다.

s = input()

# 65 ~ 90 A~Z
# 97 ~ 122 a~z
new = ""
for i in range(len(s)):
    tmp = s[i]
    asc = ord(tmp)
    if asc > 64 and asc < 91:
        num = asc + 13
        if num > 90:
            num = num - 90 + 64
    elif asc > 96 and asc < 123:
        num = asc + 13
        if num > 122:
            num = num - 122 + 96
    else:
        num = asc
    word = chr(num)
    new += word
    
print(new)

 

백준 18111 마인크래프트

첨에 어케 풀어야 될지 감도 안오더라... 구글링을 통해 도움을 받았다.

완전 탐색! 을 항상 생각해보자. 회피금지

n, m, b = map(int, input().split())

block = []
height = 0
answer = 100000000
for _ in range(n):
    block.append(list(map(int, input().split())))
    
for i in range(257):
    del_b = 0
    stack_b = 0
    
    for j in range(n):
        for k in range(m):
            if block[j][k] > i:
                del_b += block[j][k] - i
            else:
                stack_b += i - block[j][k]

    if stack_b > b + del_b:
        continue    # 다~ 쓸데없는짓이었다
    
    sec = del_b * 2 + stack_b
    if sec <= answer:
        height = i
        answer = sec
    
print(answer, height)

 

백준 18405 경쟁적 전염

 

DFS / BFS 좀 공부하고 다시 풀어봐야겠다

 

import sys

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

virus = [[0] * n] * n

for i in range(n):
    virus[i] = list(map(int, input().split()))
    
s, x, y = map(int, input().split())
loc  = [[] for _ in range(k+1)]

for i in range(n):
    for j in range(n):
        virus_kinds = virus[i][j]
        if virus_kinds != 0:
            loc[virus_kinds].append((i, j))
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]
for _ in range(s):
    for i in range(1, k+1):
        new = []
        for l in loc[i]:
            h, v = l
            for c in range(4):
                nh, nv = h + dx[c], v + dy[c]
                if not (0 <= nh < n and 0 <= nv < n):
                    continue
                if virus[nh][nv] == 0:
                    virus[nh][nv] = i
                    new.append((nh, nv))
                    
        loc[i] = new
print(virus[x-1][y-1])

 

 

백준 1092 배

 

import sys

n = int(input())

c = list(map(int, sys.stdin.readline().rstrip().split()))

m = int(input())

box = list(map(int, sys.stdin.readline().rstrip().split()))

if max(c) < max(box):
    print(-1)
else:
    cnt = 0
    box = sorted(box, reverse = True)
    c = sorted(c, reverse = True)
    while len(box) > 0:
        for x in c:
            for b in box:
                if x >= b:
                    box.remove(b)
                    break
        cnt += 1
                
                
    print(cnt)

오늘 풀었던 것중에는 이게 제일 쉬웠다.