Merge pull request #138 from alsrl8/alsrl8

skydreamer21 · web-flow · commit 31121942245a · 2022-10-24T21:11:47.000+09:00
Alsrl8
diff --git a/2022/[Week27 - Mix]/송민기/11559.py b/2022/[Week27 - Mix]/송민기/11559.py
@@ -0,0 +1,63 @@
+from collections import deque
+
+R, C = 12, 6
+grid = [list(input().rstrip()) for _ in range(R)]
+dRow, dCol = [0, 0, 1, -1], [1, -1, 0, 0]
+
+
+def get_explosive_puyo():
+    candidates = []
+    visited = [[False for _ in range(C)] for _ in range(R)]
+    for r in range(R):
+        for c in range(C):
+            if grid[r][c] == '.':
+                continue
+            elif visited[r][c]:
+                continue
+            q = deque()
+            q.append((r, c))
+            visited[r][c] = True
+            members = [(r, c)]
+            while q:
+                _r, _c = q.popleft()
+                for d in range(4):
+                    nr, nc = _r + dRow[d], _c + dCol[d]
+                    if nr < 0 or nc < 0 or nr >= R or nc >= C:
+                        continue
+                    elif grid[nr][nc] != grid[r][c]:
+                        continue
+                    elif visited[nr][nc]:
+                        continue
+                    q.append((nr, nc))
+                    visited[nr][nc] = True
+                    members.append((nr, nc))
+            if len(members) >= 4:
+                candidates.append(members)
+    return candidates
+
+
+def activate_gravity():
+    for c in range(C):
+        empty = 0
+        for r in range(R - 1, -1, -1):
+            if grid[r][c] != '.':
+                if empty == 0:
+                    continue
+                grid[r + empty][c] = grid[r][c]
+                grid[r][c] = '.'
+            else:
+                empty += 1
+
+
+answer = 0
+while True:
+    explosive_puyos = get_explosive_puyo()
+    if not explosive_puyos:
+        break
+    for puyo in explosive_puyos:
+        for r, c in puyo:
+            grid[r][c] = '.'
+    activate_gravity()
+    answer += 1
+
+print(answer)
diff --git a/2022/[Week27 - Mix]/송민기/1517.py b/2022/[Week27 - Mix]/송민기/1517.py
@@ -0,0 +1,35 @@
+N = int(input())
+A = list(map(int, input().split()))
+
+
+def divine_conquer(start, end):
+    cnt = 0
+    if start >= end:
+        return 0
+    m = (start + end) // 2
+    l, r = start, m + 1
+    cnt += divine_conquer(start, m)
+    cnt += divine_conquer(m + 1, end)
+
+    temp = []
+    while l <= m and r <= end:
+        if A[l] <= A[r]:
+            temp.append(A[l])
+            l += 1
+        else:
+            temp.append(A[r])
+            r += 1
+            cnt += (m + 1 - l)
+
+    if l <= m:
+        temp.extend(A[l:m + 1])
+    if r <= end:
+        temp.extend(A[r:end + 1])
+
+    for i in range(start, end + 1):
+        A[i] = temp[i - start]
+
+    return cnt
+
+answer = divine_conquer(0, N - 1)
+print(answer)
diff --git a/2022/[Week27 - Mix]/송민기/18808.py b/2022/[Week27 - Mix]/송민기/18808.py
@@ -0,0 +1,61 @@
+import sys
+
+N, M, K = map(int, sys.stdin.readline().split())
+paper = [[0 for _ in range(M)] for _ in range(N)]
+
+
+def is_valid(r, c, sticker):
+    if r + len(sticker) > N or c + len(sticker[0]) > M:
+        return False
+    for _r in range(len(sticker)):
+        for _c in range(len(sticker[0])):
+            if sticker[_r][_c] == 1 and paper[r + _r][c + _c] == 1:
+                return False
+    return True
+
+
+def turn_clockwise(sticker):
+    R, C = len(sticker), len(sticker[0])
+    turned = [[0 for _ in range(R)] for _ in range(C)]
+    for r in range(R):
+        for c in range(C):
+            turned[c][R - r - 1] = sticker[r][c]
+    return turned
+
+
+def put_sticker(r, c, sticker):
+    for _r in range(len(sticker)):
+        for _c in range(len(sticker[0])):
+            if sticker[_r][_c] == 1:
+                paper[r + _r][c + _c] = sticker[_r][_c]
+
+
+def search(sticker):
+    for r in range(N):
+        for c in range(M):
+            if is_valid(r, c, sticker):
+                return r, c
+    return -1, -1
+
+
+for i in range(K):
+    R, C = map(int, sys.stdin.readline().split())
+    sticker = [list(map(int, sys.stdin.readline().split())) for _ in range(R)]
+    turn_cnt, flag = 0, False
+    while turn_cnt < 4:
+        r, c = search(sticker)
+        if r < 0:
+            sticker = turn_clockwise(sticker)
+            turn_cnt += 1
+        else:
+            flag = True
+            break
+    if flag:
+        put_sticker(r, c, sticker)
+
+answer = 0
+for r in range(N):
+    for c in range(M):
+        if paper[r][c] == 1:
+            answer += 1
+print(answer)
diff --git a/2022/[Week27 - Mix]/송민기/1941.py b/2022/[Week27 - Mix]/송민기/1941.py
@@ -0,0 +1,31 @@
+from itertools import combinations
+from collections import deque
+
+grid = [input().rstrip() for _ in range(5)]
+arr = [(r, c) for r in range(5) for c in range(5)]
+comb = list(combinations(arr, 7))  # 480700
+dRow, dCol = [0, 0, 1, -1], [1, -1, 0, 0]
+
+answer = 0
+for _comb in comb:
+    cnt_s = 0
+    for r, c in _comb:
+        if grid[r][c] == 'S':
+            cnt_s += 1
+    if cnt_s < 4:
+        continue
+    r, c = _comb[0]
+    q = deque()
+    q.append((r, c))
+    visited = set()
+    visited.add((r, c))
+    while q:
+        _r, _c = q.popleft()
+        for d in range(4):
+            nr, nc = _r + dRow[d], _c + dCol[d]
+            if (nr, nc) in _comb and (nr, nc) not in visited:
+                q.append((nr, nc))
+                visited.add((nr, nc))
+    if len(visited) == 7:
+        answer += 1
+print(answer)
