[Expert Academy] 1206. [S/W 문제해결 기본] 1일차 - View

※ SW Expert 아카데미의 문제를 무단 복제하는 것을 금지합니다.

따라서 백준과 달리 문제 캡쳐는 하지 않습니다.

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

풀이

숫자을 입력 받으면 문제에서 주어진 그림과 같이 배열에 빌딩을 그려서 탐색을 하였다.

Ex)

입력은 아래와 같다.

14

0 0 3 5 2 4 9 0 6 4 0 6 0 0

그러면 나는 배열을 통해 아래와 같이 빌딩?을 표시해주었다.

00111110110100

00111110110100

00110110110100

00010110110100

00010010100100

00000010100100

00000010000000

00000010000000

00000010000000

00000000000000

그래서 0, 0 좌표 부터 254,N-1(입력되는 변수 갯수) 좌표까지 하나씩 탐색을 하였다. 배열에서 1이 찾아지면 해당 지점에서 좌우로 -2,-1,+1,+2을 하여 1이 탐색되면 다음 칸으로 넘어가 다음 칸을 탐색하는 방식으로 조망권이 확보되는 집을 찾았다. 해당 지점에서 좌우로 -2,-1,+1,+2을 하여 1이 탐색되지 않으면 +1씩 Count 해주었다.

시간복잡도는...계산이 맞는지 모르겠지만. 최대 맵의 크기 * 4로 추정된다. 시간 복잡도 계산 왜이렇게 어렵지ㅜ,ㅠ

따라서 1회 테스트 케이스에서 시간복잡도는 255*1000*4는 약 1,000,000로 추정(정확하지 않음)!

#include <stdio.h>
#include <string.h>
int map[260][1005];
int num, N, count, Flag;
 
int main()
{
 
    for (int i = 0; i < 10; i++)
    {
        count = 0;
        memset(map, 0, sizeof(map));
        scanf("%d", &num);
        Flag = 0;
 
        for (int j = 0; j < num; j++)
        {
            scanf("%d", &N);
            for (int k = 0; k < N; k++)//map에 빌딩 표시
            {
                map[k][j] = 1;
            }
        }
 
        for (int j = 0; j < 255; j++)//탐색
        {
            for (int k = 0; k < num; k++)
            {
                if (map[j][k] == 1)
                {
                    Flag = 0;
                    for (int a = 1; a < 3; a++)
                    {
                        if (map[j][k + a] == 1 || map[j][k - a] == 1)
                        // 거리 2 이내에 1감지되면 Flag처리로 무시
                        {
                            Flag = 1;
                        }
                    }
                    if (Flag == 0)
                    {
                        count++;
                    }
                }
            }
        }
 
        printf("#%d %d\n", i + 1, count);
    }
 
    return 0;
}