[백준] 16926, 1946, 1715, 16953

배열 돌리기 1 (16926번)

• 사이트/난이도: 백준 / 실버1
• 코드

# 실버1 배열 돌리기 1
import sys
input = sys.stdin.readline
n, m, r = map(int, input().split())
arr = [list(map(int, input().split())) for _ in range(n)]

def rotate():
    temp = [[0] * m for _ in range(n)]
    for i in range(min(n, m) // 2):
        x, y = i, i # 시작 x, y
        val = arr[x][y] # 이전 값 저장
        # 좌
        for j in range(i+1, n-i):
            x = j
            temp[x][y] = val
            val = arr[x][y]
        # 하
        for j in range(i+1, m-i):
            y = j
            temp[x][y] = val
            val = arr[x][y]
        # 우
        for j in range(i+1, n-i):
            x = n - j - 1
            temp[x][y] = val
            val = arr[x][y]

        # 상
        for j in range(i+1, m-i):
            y = m - j - 1
            temp[x][y] = val
            val = arr[x][y]
    return temp

for _ in range(r):
    arr = rotate()

for i in arr:
    print(*i)

• 느낀점
  • 배열을 반시계방향으로 한칸씩 돌리는 문제인데 안에 있는 배열까지 다 돌려줘야 되므로
  • min(n, m) // 2 만큼 돌려야 된다.
  • 좌, 하, 우, 상 순으로 인덱스 비교하며 생각하면 풀 수 있는 문제

신입사원 (1946번)

• 사이트/난이도: 백준/실버1
• 코드

# 실버1 신입사원
import sys
input = sys.stdin.readline
t = int(input())
for _ in range(t):
    n = int(input())
    scores = []
    for _ in range(n):
        a, b = map(int, input().split())
        scores.append((a,b))
    scores.sort()
    count = 1
    min_val = scores[0][1]
    for i in range(1, n):
        if  min_val > scores[i][1]:
            min_val = scores[i][1]
            count += 1
    print(count)

• 느낀점
  • 시간초과에 유의해야되는 그리디 + 정렬 문제
  • 먼저 서류 점수 순으로 정렬 후 면접 시험 점수는 자기 보다 앞에있는 (서류심사 점수가 높은) 값들 끼리만 비교하여 신입사원 수를 증가시켜준다. 이때 변수 min_val 을 이용해 최소값을 저장하여 시간초과 문제를 해결해주었다.

카드 정렬하기 (1715번)

• 사이트/난이도: 백준/골드4
• 코드

# 골드4 카드 정렬하기
import sys
import heapq
input = sys.stdin.readline

n = int(input())
cards = []
for _ in range(n):
    heapq.heappush(cards, int(input()))

if len(cards) == 1:
    print(0)
else:
    answer = 0
    while len(cards) > 1:
        min1 = heapq.heappop(cards)
        min2 = heapq.heappop(cards)
        answer += min1 + min2
        heapq.heappush(cards, min1 + min2)
    print(answer)

• 느낀점
  • 시간초과에 주의해야되는 그리디 문제
  • 어차피 최소 비교하려면 카드 수가 가장 적은 거부터 비교해야 되므로 알아서 정렬이 되는 최소 힙을 사용한다.

A → B (16953번)

• 사이트/난이도: 백준 / 실버2
• 코드

# 실버2 A->B
# bfs (bottom-up)
import sys
from collections import deque
input = sys.stdin.readline
a, b = map(int, input().split())

def bfs():
    q = deque([])
    q.append((a, 0))
    while q:
        now, count = q.popleft()
        if now == b:
            return count + 1
        elif now > b:
            continue
        else:
            if now * 2 <= b:
                q.append((now * 2, count + 1))
            if int(str(now) + '1') <= b:
                q.append((int(str(now) + '1'), count + 1))
    return -1
print(bfs())

# 그리디 방식 (top-down)
a,b = map(int,input().split())
r = 1
while(b!=a):
    r+=1
    temp = b
    if b%10 == 1:
        b//=10
    elif b%2 == 0:
        b//=2
    
    if temp == b:
        print(-1)
        break
else:
    print(r)

• 느낀점
  • 해당 문제는 2가지 방식으로 풀 수 있다. 바텀 업으로 bfs 방식, 탑다운으로 그리디 방식
  • 난 일단 바텀 업으로 bfs로 풀었는데 생각해보니 탑다운으로 그리디 방식으로 풀 수 있는걸 다른 사람 풀이 보고 알 수 있었다.