어디에 단어가 들아갈 수 있을까 C++(SW Expert Academy)

난이도 : D2

문제번호 : 1979

※ 저의 풀이가 무조건적인 정답은 아닙니다.

다른 코드가 좀더 효율적이고 좋을 수 있습니다.

다른사람들의 풀이는 언제나 참고만 하시기 바랍니다.

문제 주소 및 출처입니다.

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5PuPq6AaQDFAUq&categoryId=AV5PuPq6AaQDFAUq&categoryType=CODE

SW Expert Academy

---

목차

1. 문제 설명

2. 문제 해석

3. 소스 코드

---

1. 문제 설명

N X N 크기의 단어 퍼즐을 만들려고 한다. 입력으로 단어 퍼즐의 모양이 주어진다. 주어진 퍼즐 모양에서 특정 길이 K를 갖는 단어가 들어갈 수 있는 자리의 수를 출력하는 프로그램을 작성하라.

N = 5, K = 3 이고, 퍼즐의 모양이 아래 그림과 같이 주어졌을 때

길이가 3 인 단어가 들어갈 수 있는 자리는 2 곳(가로 1번, 가로 4번)이 된다.
 

제약사항

1. N은 5 이상 15 이하의 정수이다. (5 ≤ N ≤ 15) 2. K는 2 이상 N 이하의 정수이다. (2 ≤ K ≤ N)

입력

입력은 첫 줄에 총 테스트 케이스의 개수 T가 온다. 다음 줄부터 각 테스트 케이스가 주어진다. 테스트 케이스의 첫 번째 줄에는 단어 퍼즐의 가로, 세로 길이 N 과, 단어의 길이 K 가 주어진다. 테스트 케이스의 두 번째 줄부터 퍼즐의 모양이 2차원 정보로 주어진다. 퍼즐의 각 셀 중, 흰색 부분은 1, 검은색 부분은 0 으로 주어진다.

출력

테스트 케이스 t에 대한 결과는 “#t”을 찍고, 한 칸 띄고, 정답을 출력한다. (t는 테스트 케이스의 번호를 의미하며 1부터 시작한다.)

예시

입력	출력
10 5 3 0 0 1 1 1 1 1 1 1 0 0 0 1 0 0 0 1 1 1 1 1 1 1 0 1 5 3 1 0 0 1 0 1 1 0 1 1 1 0 1 1 1 0 1 1 0 1 0 1 1 1 0	#1 2 #2 6

 

---

2. 문제풀이

가로 세로방향으로 이동하면서 k만큼의 단어가 들어갈수 있는지 체크함으로써 풀었습니다. 1이라면 count를 1개씩 증가시키고 0을만나게 된다면 k와 count를 비교합니다. 일치한다면 answer+1합니다. 0을 만나게되면 k와 같든 같지않은 count를 초기화합니다.   마지막반복문이 끝나고나서 마지막까지 데이터를 넣을수 있었을경우도 있으므로 반복문이 끝나고 나서 count를 위와같이 비교합니다.

 

---

3. 소스코드

#include <iostream>
#include <string>
 
using namespace std;
//D2 1979 어디에 단어가 들어갈 수 있을까
int main() {
    //퍼즐의 최대크기는 15이므로 15*15로 만들어 준다.
    int length, n, k, list[15][15];
    cin >> length;
    //전체반복횟수 test case만큼
    for (int i = 1; i <= length; i++) {
        cin >> n >> k;
        int answer = 0;
        //퍼즐상태를 입력받는다.
        for (int j = 0; j < n; j++) {
            int count = 0;
            for (int z = 0; z < n; z++)
                cin >> list[j][z];
        }
        //x와 y축을 돌면서 계산한다.
        for (int j = 0; j < n; j++) {
            int count1 = 0, count2 = 0;
            for (int z = 0; z < n; z++) {
                //값을 넣을수있다면 카운트
                if (list[z][j])      count1++;
                //값을 넣을수 없다면 체크한다.
                else {
                    //원하는 크기만큼 넣을수 있다면 answer증가
                    if (count1 == k)       answer++;
                    //측정하는 변수 초기화
                    count1 = 0;
                }
                //위와 동일하다.
                if (list[j][z])    count2++;
                else {
                    if (count2 == k)      answer++;
                    count2 = 0;
                }
            }// for z end
            //마지막부분까지 넣을수있었다면 체크해야한다.
            // 마지막 뒷부분이 k만큼인지 체크하여 answer 증가
            if (count1 == k)       answer++;
            if (count2 == k)      answer++;
        }// for j end
        cout << "#" << i << " " << answer << endl;
    }// for i end
    return 0;
}