[Codeforces] Hello 2022 후기
A. Stable Arrangement of Rooks
1 <= t <= 100 (test case)
1 <= k <= n <= 40 인 n, k 가 주어짐
n x n 크기의 체스판 위에 룩을 k개 올려놓을 때, stable하게 놓는 방법 중 하나를 출력하면 된다.
stable 이란
1. 모든 룩들이 서로 위치한 행과 열이 겹치지 않는다
2. 어느 하나의 룩을 상하좌우 한칸 움직였을 때 그 칸의 행과 열에 위치한 룩이 없다.
이 두가지를 만족하는 상태를 말한다.
처음엔 브루트포스 인 줄 알고 막 들이댔는데...
k개의 룩의 위치를 고르는 부분을 짜려다 좀 이상함을 깨달았다.
t(n^2)Ck k * .. combinations...
일단 시간복잡도는 심각하게 느렸다
다시 그림들을 그려본 결과
대각선으로 놓으면 된다는 걸 알았다..
한 생각에 빠지니까 되돌아가서 생각하는 게 잘 안된다.
t = int(input())
for _ in range(t):
n,k = map(int,input().split())
if n%2 == 0:
if k <= n//2:
cnt = 0
for i in range(n):
for j in range(n):
if (i+1)%2 != 0 and (j+1)%2 != 0 and (i==j) and cnt < k:
print("R",end="")
cnt+=1
else:
print(".",end="")
print()
else:
print(-1)
else:
if k <= (n//2 + 1):
cnt = 0
for i in range(n):
for j in range(n):
if (i+1)%2 != 0 and (j+1)%2 != 0 and (i==j) and cnt < k:
print("R", end="")
cnt += 1
else:
print(".", end="")
print()
else:
print(-1)
i==j 이고 i,j가 홀수 번째 행,열에 있으면 R을 출력했다.
결과
1솔
브루트포스를 하기전에 시간복잡도를 확실히 계산하자.
Author And Source
이 문제에 관하여([Codeforces] Hello 2022 후기), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@yogjin/Codeforces-Hello-2022-후기저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)