[SWEA]1979. 어디에 단어가 들어갈 수 있을까

1979. 어디에 단어가 들어갈 수 있을까

N x N 크기의 단어 퍼즐을 만들려고 합니다.

주어진 퍼즐 모양에서 특정 길이 k를 가즌 단어가 들어갈 수 있는 자리의 수를 출력하는 프로그램을 만들어야 합니다.

생각해보기

우선 N x N크기의 이차원 배열을 만들고, 0과 1로 구성된 값들이 주어지니 이 배열을 읽으면서 1이 K번 반복되면 카운트를 하고 그 카운트를 하는데 조건으로 다음수가 또 1이 나오지 않게 구성해야한다고 생각했습니다.

처음에 많이 헤맸던 부분이 행을 기준으로는 순서대로 읽어서 판단하는데 열 기준으로도 읽어서 판단해야한다는 것이었습니다.

그래서 일단 규칙성을 찾기 위해서 (a, b)형태로 나열해봤습니다.

(0, 0)(0, 1)(0, 2)(0, 3)(0, 4)

(1, 0)(1, 1)(1, 2)(1, 3)(1, 4)

(2, 0)(2, 1)(2, 2)(2, 3)(2, 4)

(3, 0)(3, 1)(3, 2)(3, 3)(3, 4)

(4, 0)(4, 1)(4, 2)(4, 3)(4, 4)

그러니까 저 배열을 puzzle이라고 칭한다면 puzzle[a][b] 일때, 가로로 읽을 때는 [b]가 변하고 세로로 읽을 때는 [a]가 변합니다.

for문으로 puzzle[a][b], puzzle[b][a]이라고 정의해서 풀면 되겠습니다.

매번 시간이 부족하다고 생각해서 문제에 대해서 진득하게 생각해보고 풀기보다는 우선 식을 먼저 세우고 시작해서 시간이 오래걸립니다.
이 문제도 4시간 넘게 고민하면서 위의 생각하기 처럼 정리가 됐습니다. 먼저 글로 문제를 이해하고 필요한 규칙을 찾으려고 해야겠습니다.

T = int(input())
for i in range(1, T+1):
    N, K = map(int, input().split())
    space = []
    for _ in range(N):
        Nn = list(map(int, input().split()))
        space.append(Nn)
    print(space)
    sol = 0
    for v in space:
        s = ""
        for x in v:
            s += str(x)
            if "1"*K in s:
                sol += 1
        print(s)        
            
                
    print(s, sol)
    
-----------------------------------------------
for t in range(int(input())):
  n,k = map(int,input().split())
  a = [list(map(int,input().split())) for _ in range(n)]
  res = 0
  for i in range(n):
    x,y = 0,0
    for j in range(n):
      if a[i][j] == 1:
        x += 1
      elif a[i][j] == 0:
        if x == k:
          res += 1
        x = 0
      if a[j][i] == 1:
        y += 1
      elif a[j][i] == 0:
        if y == k:
          res += 1
        y = 0
    if x == k:
      res += 1
    if y == k:
      res += 1
  print(f'#{t+1} {res}')
---------------------------------------------
T = int(input())
for i in range(1, T+1):
    N, K = map(int, input().split())
    space = []
    for _ in range(N):
        Nn = list(map(int, input().split()))
        space.append(Nn)
    rcount = 0
    for a in range(N):
        count = 0
        count2 = 0
        for b in range(N):
            if space[a][b] == 1:
                count += 1
                if count == K:
                    rcount += 1
                elif count > K:
                    rcount -= 1
                    count = 0
            else:
                count = 0   
            if space[b][a] == 1:
                count2 += 1
                if count2 == 3:
                    rcount += 1
                elif count2 > K:
                    rcount -= 1
                    count2 = 0
            else:
                count2 = 0

    print(f'#{i} {rcount}')

---

최종 정리

T = int(input())
for tc in range(1, T+1):
    N, K = map(int, input().split())
    puzzle = [list(map(int, input().split())) for _ in range(N)]
    answer = 0
    for i in range(N):
        count = 0
        for j in range(N):
            if puzzle[i][j] == 1:
                count += 1
            if puzzle[i][j] == 0 or j == N - 1:
                if count == K:
                    answer += 1
                count = 0
        for j in range(N):
            if puzzle[j][i] == 1:
                count += 1
            if puzzle[j][i] == 0 or j == N - 1:
                if count == K:
                    answer += 1
                count = 0
    print(f'#{tc} {answer}')