μΌμ± SW μλ ν μ€νΈ κΈ°μΆ λ¬Έμ - 21608λ² μμ΄ μ΄λ±νκ΅
21608λ²: μμ΄ μ΄λ±νκ΅
μμ΄ μ΄λ±νκ΅μλ κ΅μ€μ΄ νλ μκ³ , κ΅μ€μ N×N ν¬κΈ°μ 격μλ‘ λνλΌ μ μλ€. νκ΅μ λ€λλ νμμ μλ N2λͺ μ΄λ€. μ€λμ λͺ¨λ νμμ μ리λ₯Ό μ νλ λ μ΄λ€. νμμ 1λ²λΆν° N2λ²κΉμ§ λ²νΈ
www.acmicpc.net
λ¬Έμ
μμ΄ μ΄λ±νκ΅μλ κ΅μ€μ΄ νλ μκ³ , κ΅μ€μ N×N ν¬κΈ°μ 격μλ‘ λνλΌ μ μλ€. νκ΅μ λ€λλ νμμ μλ N2λͺ μ΄λ€. μ€λμ λͺ¨λ νμμ μ리λ₯Ό μ νλ λ μ΄λ€. νμμ 1λ²λΆν° N2λ²κΉμ§ λ²νΈκ° λ§€κ²¨μ Έ μκ³ , (r, c)λ rν cμ΄μ μλ―Ένλ€. κ΅μ€μ κ°μ₯ μΌμͺ½ μ μΉΈμ (1, 1)μ΄κ³ , κ°μ₯ μ€λ₯Έμͺ½ μλ« μΉΈμ (N, N)μ΄λ€.
μ μλμ νμμ μμλ₯Ό μ νκ³ , κ° νμμ΄ μ’μνλ νμ 4λͺ λ λͺ¨λ μ‘°μ¬νλ€. μ΄μ λ€μκ³Ό κ°μ κ·μΉμ μ΄μ©ν΄ μ ν΄μ§ μμλλ‘ νμμ μ리λ₯Ό μ νλ €κ³ νλ€. ν μΉΈμλ νμ ν λͺ μ μλ¦¬λ§ μμ μ μκ³ , |r1 - r2| + |c1 - c2| = 1μ λ§μ‘±νλ λ μΉΈμ΄ (r1, c1)κ³Ό (r2, c2)λ₯Ό μΈμ νλ€κ³ νλ€.
- λΉμ΄μλ μΉΈ μ€μμ μ’μνλ νμμ΄ μΈμ ν μΉΈμ κ°μ₯ λ§μ μΉΈμΌλ‘ μ리λ₯Ό μ νλ€.
- 1μ λ§μ‘±νλ μΉΈμ΄ μ¬λ¬ κ°μ΄λ©΄, μΈμ ν μΉΈ μ€μμ λΉμ΄μλ μΉΈμ΄ κ°μ₯ λ§μ μΉΈμΌλ‘ μ리λ₯Ό μ νλ€.
- 2λ₯Ό λ§μ‘±νλ μΉΈλ μ¬λ¬ κ°μΈ κ²½μ°μλ νμ λ²νΈκ° κ°μ₯ μμ μΉΈμΌλ‘, κ·Έλ¬ν μΉΈλ μ¬λ¬ κ°μ΄λ©΄ μ΄μ λ²νΈκ° κ°μ₯ μμ μΉΈμΌλ‘ μ리λ₯Ό μ νλ€.
μλ₯Ό λ€μ΄, N = 3μ΄κ³ , νμ N2λͺ μ μμμ κ° νμμ΄ μ’μνλ νμμ΄ λ€μκ³Ό κ°μ κ²½μ°λ₯Ό μκ°ν΄λ³΄μ.
νμμ λ²νΈ | μ’μνλ νμμ λ²νΈ |
4 | 2, 5, 1, 7 |
3 | 1, 9, 4, 5 |
9 | 8, 1, 2, 3 |
8 | 1, 9, 3, 4 |
7 | 2, 3, 4, 8 |
1 | 9, 2, 5, 7 |
6 | 5, 2, 3, 4 |
5 | 1, 9, 2, 8 |
2 | 9, 3, 1, 4 |
μ΄μ νμμ λ§μ‘±λλ₯Ό ꡬν΄μΌ νλ€. νμμ λ§μ‘±λλ μ리 λ°°μΉκ° λͺ¨λ λλ νμ ꡬν μ μλ€. νμμ λ§μ‘±λλ₯Ό ꡬνλ €λ©΄ κ·Έ νμκ³Ό μΈμ ν μΉΈμ μμ μ’μνλ νμμ μλ₯Ό ꡬν΄μΌ νλ€. κ·Έ κ°μ΄ 0μ΄λ©΄ νμμ λ§μ‘±λλ 0, 1μ΄λ©΄ 1, 2μ΄λ©΄ 10, 3μ΄λ©΄ 100, 4μ΄λ©΄ 1000μ΄λ€.
νμμ λ§μ‘±λμ μ΄ ν©μ ꡬν΄λ³΄μ.
μ λ ₯
첫째 μ€μ Nμ΄ μ£Όμ΄μ§λ€. λμ§Έ μ€λΆν° N2κ°μ μ€μ νμμ λ²νΈμ κ·Έ νμμ΄ μ’μνλ νμ 4λͺ μ λ²νΈκ° ν μ€μ νλμ© μ μλμ΄ μ리λ₯Ό μ ν μμλλ‘ μ£Όμ΄μ§λ€.
νμμ λ²νΈλ μ€λ³΅λμ§ μμΌλ©°, μ΄λ€ νμμ΄ μ’μνλ νμ 4λͺ μ λͺ¨λ λ€λ₯Έ νμμΌλ‘ μ΄λ£¨μ΄μ Έ μλ€. μ λ ₯μΌλ‘ μ£Όμ΄μ§λ νμμ λ²νΈ, μ’μνλ νμμ λ²νΈλ N2λ³΄λ€ μκ±°λ κ°μ μμ°μμ΄λ€. μ΄λ€ νμμ΄ μκΈ° μμ μ μ’μνλ κ²½μ°λ μλ€.
μΆλ ₯
첫째 μ€μ νμμ λ§μ‘±λμ μ΄ ν©μ μΆλ ₯νλ€.
μ ν
- 3 ≤ N ≤ 20
μμ μ λ ₯1
3
4 2 5 1 7
3 1 9 4 5
9 8 1 2 3
8 1 9 3 4
7 2 3 4 8
1 9 2 5 7
6 5 2 3 4
5 1 9 2 8
2 9 3 1 4
μμ μΆλ ₯1
54
νμ΄
1. μ,ν,μ’,μ°λ₯Ό νμνλ©΄μ tmp λ°°μ΄μ like(μΈμ ν μΉΈμ μ‘΄μ¬νλ μ νΈ νμμ), blank(λΉ μΉΈμ), r, c μ’νλ₯Ό λ΄λλ€
2. tmp λ°°μ΄ μ λ ¬ : likeμ blankλλ΄λ¦Όμ°¨μμΌλ‘ μ λ ¬, μ’ν rκ³Ό cλ μ€λ¦μ°¨μ μ λ ¬
- lambda ν¨μ μ¬μ© : - κΈ°νΈ λΆμ΄λ©΄ λ΄λ¦Όμ°¨μμΌλ‘ μ λ ¬νλ€
3. μ λ ¬ ν, κ°μ₯ μμ μλ 리μ€νΈμ νκ³Ό μ΄ λ²νΈμ νμμ μνλ€
- tmp[0][2] λ r, tmp[0][3]μ cλ₯Ό μλ―Έ
- st_num[0] μ νμμ λ²νΈλ₯Ό μλ―Έ
4. μ νΈλ μ΄ν© ꡬνκΈ°
1) μνμ’μ° νμνλ©° μ νΈνλ νμμ μλ₯Ό ꡬνλ€
2) 1μ΄λ©΄ 1, 2μ΄λ©΄ 10, 3μ΄λ©΄ 100, 4μ΄λ©΄ 1000μ΄λ―λ‘ 10μ nμ κ³±μ ꡬν΄μ£Όλ©΄ λλ€. λ°λΌμ 10 ** (like - 1) μ ν΄μ€λ€
3) νμμ μλ§νΌ λ°λ³΅νλ©΄μ 10 ** (like - 1) ν΄μ€ κ°μ answerμ λν΄μ μ΄ ν©μ ꡬνλ€
# μΌμ± SW μλ ν
μ€νΈ κΈ°μΆ λ¬Έμ
# λ°±μ€ 21608λ². μμ΄ μ΄λ±νκ΅
# ꡬν
n = int(input())
students = [list(map(int, input().split())) for _ in range(n ** 2)]
classroom = [[0] * n for _ in range(n)] # κ΅μ€
# μνμ’μ°
dr = [0, 0, 1, -1]
dc = [1, -1, 0, 0]
for i in range(n ** 2):
st_num = students[i]
tmp = [] # μ νΈ νμμ, λΉμΉΈ μ, μ’ν λ΄μ λ°°μ΄
for r in range(n):
for c in range(n):
if classroom[r][c] == 0:
like = 0
blank = 0
for k in range(4):
nr, nc = r + dr[k], c + dc[k]
if 0 <= nr < n and 0 <= nc < n:
if classroom[nr][nc] in st_num[1:]:
like += 1
if classroom[nr][nc] == 0:
blank += 1
tmp.append([like, blank, r, c])
tmp.sort(key = lambda x : (-x[0], -x[1], x[2], x[3]))
# μ λ ¬ ν κ°μ₯ μμ μλ 리μ€νΈμ νκ³Ό μ΄ λ²νΈμ νμ μν
classroom[tmp[0][2]][tmp[0][3]] = st_num[0]
answer = 0
students.sort()
for r in range(n):
for c in range(n):
like = 0
for i in range(4):
nr, nc = r + dr[i], c + dc[i]
if 0 <= nr < n and 0 <= nc < n:
if classroom[nr][nc] in students[classroom[r][c] - 1]:
like += 1
if like != 0:
answer += 10 ** (like - 1)
print(answer)
μκ³ λ¦¬μ¦ λΆλ₯
- ꡬν