240403 - 스티커 붙이기, 극장 좌석, 트리 순회

[robert-min]

문제

1. boj18808 - 스티커 붙이기 링크
2. boj2302 - 극장 좌석 링크
3. boj22856 - 트리 순회 링크

[robert-min]

boj18808 - 스티커 붙이기

• 배열 90도 회전

  
  N = len(arr)
  M = len(arr[0])

temp = [[0]] * N for _ in range(M)] for i in range(N): for j in range(M): temp[j][N-i-1] = arr[i][j]

```python
"""
Return: 스티커가 붙은 칸의 개수
- 왼쪽 위에서부터 스티커가 붙을 수 있는지 확인
- 붙일 수 있으면 붙임
- 못붙이면 90도씩 회전 후 반복
- 모든 스티커 확인 후 영역 확인

1. 모든 스티커 확인
2. 왼쪽 위에서부터 스티커 붙일 수 있는지 확인 check
- visited
3. 스티커를 붙이지 못하면 회전 rotate
- dx, dy -> move = 0, 1, 2, 0 ..
- 90도 회전 
- 오른 -> 아래 -> 왼쪽 -> 위 -> 오른
dx = [0, 1, 0, -1]
dy = [1, 0, -1, 0] k값이 +1, k == 4 -> k =0

4. 모든 스티커가 붙인다음 붙여진 영역 확인 find_area
"""
import sys
input = sys.stdin.readline

def checking(temp, sticker):
    for sy in range(len(sticker)):
        for sx in range(len(sticker[0])):
            if temp[i+sy][j+sx] + sticker[sy][sx] > 1:
                return False
    return True

def attach(temp, sticker):
    for sy in range(len(sticker)):
        for sx in range(len(sticker[0])):
            temp[i+sy][j+sx] += sticker[sy][sx]
    return

def rotate_90(arr):
    n = len(arr)
    m = len(arr[0])

    result = [[0]*n for _ in range(m)]

    for i in range(n):
        for j in range(m):
            result[j][n-i-1] = arr[i][j]
    return result

Y, X, k = map(int, input().split())
notebook = [[0] * X for _ in range(Y)]

for _ in range(k):
    y, x = map(int, input().split())
    sticker = [list(map(int, input().split())) for _ in range(y)]
    chk = False
    cnt = 0
    while cnt < 4:
        if chk == True:
            break
        for i in range(Y - len(sticker) + 1):
            if chk == True:
                break
            for j in range(X - len(sticker[0]) + 1):
                if checking(notebook, sticker):
                    attach(notebook, sticker)
                    chk = True
                    break
        sticker = rotate_90(sticker)
        cnt += 1

answer = 0
for i in range(Y):
    for j in range(X):
        answer += notebook[i][j]

print(answer)

[robert-min]

boj2302 - 극장 좌석

"""
Return: 좌석에 앉을 수 있는 방법의 가짓 수
- 본인 자리 양 옆에 앉을 수 있음 i-1, i, i+1
- 고정석은 해당 자리만 앉을 수 있음

1번자리 1, 2
2번자리 1, 2, 3
3번자리 2, 3 
4번자리(고정) 4
5번자리 5, 6
6번자리 5, 6
7번자리(고정) 7
8번자리 8, 9
9번자리 8, 9

dp[i][0] : i번째 자리에서 자리를 바꾸지 않는 경우의 수
dp[i][1] : i번째 자리에서 자리를 바꾸는 경우

i번 티켓을 받은 사람이 i번자리 앉는 경우
dp[i-1][0] + dp[i-1][1]
vip 좌석이 잇을 경우 : dp[i-1][0]

i번 티켓을 받은 사람이 i번자리 앉지 않는 경우
dp[i-1][0] (이미 이전에 바꾸지 않았으니까)
vip 좌석이 잇을 경우 : 0

경우의 수 저장 
"""
N = int(input())
M = int(input())
default = []
for _ in range(M):
    default.append(int(input()))

dp = [[0] * 2 for _ in range(N+1)]

dp[1][0] = 1
dp[1][1] = 0

for d in default:
    dp[d][1] = -1
# print(dp)

for i in range(2, N+1):
    if dp[i][1] == -1:  # 현 좌석이 vip 석이 아닌경우
        if dp[i-1][1] != -1:    # 전 좌석이 vip가 아니면
            dp[i][0] = dp[i-1][0] + dp[i-1][1]
            dp[i][1] = -1 # 확인
        else:
            dp[i][0] = dp[i-1][0]   # vip 좌석이 있을 경우
            dp[i][1] = -1
    else:
        if dp[i-1][1] != -1:
            dp[i][0] = dp[i-1][0] + dp[i-1][1]
            dp[i][1] = dp[i-1][0]
        else:
            dp[i][0] = dp[i-1][0]
            dp[i][1] = 0

if dp[N][1] == -1:
    print(dp[N][0])
else:
    print(dp[N][0]+dp[N][1])

[robert-min]

boj22856 - 트리 순회

"""
Return : 유사 중위 순회를 하면서 이동한 횟수
- trees

- visited가 방문다 되면 종료
- dfs왼쪽 노드 방문하면서 재귀할 때 마다 출력
"""
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

N = int(input())
trees = [[] for _ in range(N+1)]
for _ in range(N):
    node, left, right = map(int, input().split())
    trees[node].append(left)
    trees[node].append(right)

visited = []
cnt1 = 0
def dfs(now):
    global cnt1
    cnt1 += 1
    visited.append(now)
    if trees[now][0] != -1:
        dfs(trees[now][0])
        cnt1 += 1
        visited.append(now)

    if trees[now][1] != -1:
        dfs(trees[now][1])
        cnt1 += 1
        visited.append(now)

dfs(1)

cnt2 = 0
def dfs_right(now):
    global cnt2
    if trees[now][1] != -1:
        dfs_right(trees[now][1])
    cnt2 += 1

dfs_right(1)
print(cnt1 - cnt2)