SWEA_4615_재미있는오셀로게임, SWEA_2117_홈방범서비스

SWEA_4615_재미있는오셀로게임

재미 한탱이도 없음

 

SW Expert Academy

 

문제

오셀로라는 게임은 흑돌과 백돌을 가진 사람이 번갈아가며 보드에 돌을 놓아서 최종적으로 보드에 자신의 돌이 많은 사람이 이기는 게임이다.
보드는 4x4, 6x6, 8x8(가로, 세로 길이) 크기를 사용한다. 6x6 보드에서 게임을 할 때, 처음에 플레이어는 다음과 같이 돌을 놓고 시작한다(B : 흑돌, W : 백돌).
4x4, 8x8 보드에서도 동일하게 정가운데에 아래와 같이 배치하고 시작한다.

그리고 흑, 백이 번갈아가며 돌을 놓는다.
처음엔 흑부터 시작하는데 이 때 흑이 돌을 놓을 수 있는 곳은 다음과 같이 4군데이다.

플레이어는 빈공간에 돌을 놓을 수 있다.
단, 자신이 놓을 돌과 자신의 돌 사이에 상대편의 돌이 있을 경우에만 그 곳에 돌을 놓을 수 있고, 그 때의 상대편의 돌은 자신의 돌로 만들 수 있다.
(여기에서 "사이"란 가로/세로/대각선을 의미한다.)
(2, 3) 위치에 흑돌을 놓은 후의 보드는 다음과 같다.

이런 식으로 번갈아가며 흑, 백 플레이어가 돌을 놓는다.
만약 돌을 놓을 곳이 없다면 상대편 플레이어가 다시 돌을 놓는다.
보드에 빈 곳이 없거나 양 플레이어 모두 돌을 놓을 곳이 없으면 게임이 끝나고 그 때 보드에 있는 돌의 개수가 많은 플레이어가 승리하게 된다.

 

 

 

입력

첫 번째 줄에 테스트 케이스의 수 T가 주어진다.
각 테스트 케이스의 첫 번째 줄에는 보드의 한 변의 길이 N과 플레이어가 돌을 놓는 횟수 M이 주어진다. N은 4, 6, 8 중 하나이다.
그 다음 M줄에는 돌을 놓을 위치와 돌의 색이 주어진다.
돌의 색이 1이면 흑돌, 2이면 백돌이다.
만약 3 2 1이 입력된다면 (3, 2) 위치에 흑돌을 놓는 것을 의미한다.
돌을 놓을 수 없는 곳은 입력으로 주어지지 않는다.

 

해결방법

- 

 

출력

각 테스트 케이스마다 게임이 끝난 후 보드 위의 흑돌, 백돌의 개수를 출력한다.
흑돌이 30개, 백돌이 34인 경우 30 34를 출력한다.

 

 

 

코드

import sys
sys.stdin = open('4615_input.txt', 'r')

T = int(input())

for test_case in range(1, T+1):
    N, M = map(int, input().split())
    board = [[0] * N for _ in range(N)]
    d = [[0, 1], [0, -1], [1, 0], [-1, 0], [1, 1], [1, -1], [-1, 1], [-1, -1]]

    # 보드의 초기 배치
    board[N // 2 - 1][N // 2 - 1] = 2
    board[N // 2 - 1][N // 2] = 1
    board[N // 2][N // 2 - 1] = 1
    board[N // 2][N // 2] = 2


    for m in range(M):
        i, j, color = map(int, input().split())
        i -= 1
        j -= 1

        # 돌 놓기
        board[i][j] = color

        # 현재위치를 기준으로 색이 바뀔 돌이 있는지 탐색하면서 색 변경
        for di, dj in d:
            ni = i + di
            nj = j + dj
            cnt = 0

            while 0 <= ni < N and 0 <= nj < N and board[ni][nj] != 0 and board[ni][nj] != color:
                ni += di
                nj += dj
                cnt += 1

            # 영역 안이면
            if 0 <= ni < N and 0 <= nj < N and board[ni][nj] == color:
                # 새로운 좌표까지 board의 값을 변경
                for _ in range(cnt):
                    ni -= di
                    nj -= dj
                    board[ni][nj] = color


    black, white = 0, 0
    for i in range(N):
        for j in range(N):
            if board[i][j] == 1:
                black += 1
            if board[i][j] == 2:
                white += 1

    print(f'#{test_case} {black} {white}')

 

 

 

 

 

SWEA_2117_홈방범서비스

 

SW Expert Academy

 

 

문제

N*N 크기의 도시에 홈방범 서비스를 제공하려고 한다.
홈방범 서비스는 운영 상의 이유로 아래의 파란색 부분과 같이 마름모 모양의 영역에서만 제공된다.

또한, 홈방범 서비스를 제공하기 위해서는 운영 비용이 필요하다.
아래와 같이 서비스 영역의 크기 K 가 커질수록 운영 비용이 커진다.
운영 비용은 서비스 영역의 면적과 동일하며, 아래와 같이 구할 수 있다.
운영 비용 = K * K + (K - 1) * (K - 1)
운영 영역의 크기 K 는 1 이상의 정수이다.

 - K = 1 일 때, 운영 비용은 1 이다.
 - K = 2 일 때, 운영 비용은 5 이다.
 - K = 3 일 때, 운영 비용은 13 이다.
 - K = 4 일 때, 운영 비용은 25 이다.

 

아래과 같이 도시를 벗어난 영역에 서비스를 제공해도 운영 비용은 변경되지 않는다.
아래의 경우 K = 3 이므로, 운영 비용은 13 이다.
 

홈방범 서비스를 제공받는 집들은 각각 M의 비용을 지불할 수 있어, 보안회사에서는 손해를 보지 않는 한 최대한 많은 집에 홈방범 서비스를 제공하려고 한다.
도시의 크기 N과 하나의 집이 지불할 수 있는 비용 M, 도시의 정보가 주어진다.
이때, 손해를 보지 않으면서 홈방범 서비스를 가장 많은 집들에 제공하는 서비스 영역을 찾고,
그 때의 홈방범 서비스를 제공 받는 집들의 수를 출력하는 프로그램을 작성하라.


[예시]
예를 들어, [Fig. 4]과 같이 N이 8인 도시의 정보가 주어지고, 하나의 집이 지불할 수 있는 비용 M이 3이라고 생각해 보자.

아래와 같이 서비스 영역 K = 2로 하여 홈방범 서비스를 제공할 때는 최대 3개의 집까지 서비스 제공이 가능하다.
이 경우 보안회사의 이익은 4가 되어 손해를 보지 않고 서비스 제공이 가능하다.
보안회사의 이익(4) = 서비스 제공받는 집들을 통해 얻는 수익(3*3) - 운영 비용(5)

아래는 서비스 영역 K = 3으로 하여 홈방범 서비스를 제공할 때에 최대 5개의 집까지 서비스 제공이 가능한 경우 중 하나이다.
보안회사의 이익(2) = 서비스 제공받는 집들을 통해 얻는 수익(3*5) - 운영 비용(13)

위의 예에서, 보안회사가 손해를 보지 않고 서비스 가능한 최대 집의 수는 5이며, 5가 정답이 된다.

 

 

제약사항

1. 시간제한 : 최대 50개 테스트 케이스를 모두 통과하는데, C/C++/Java 모두 3초
2. 도시의 크기 N은 5 이상 20 이하의 정수이다. (5 ≤ N ≤ 20)
3. 하나의 집이 지불할 수 있는 비용 M은 1 이상 10 이하의 정수이다. (1 ≤ M ≤ 10)
4. 홈방범 서비스의 운영 비용은 서비스 영역의 면적과 동일하다.
5. 도시의 정보에서 집이 있는 위치는 1이고, 나머지는 0이다.
6. 도시에는 최소 1개 이상의 집이 존재한다.

 

입력

입력의 맨 첫 줄에는 총 테스트 케이스의 개수 T가 주어지고, 그 다음 줄부터 T개의 테스트 케이스가 주어진다.
각 테스트 케이스의 첫 번째 줄에는 도시의 크기 N과 하나의 집이 지불할 수 있는 비용 M이 주어진다.
그 다음 줄부터 N*N 크기의 도시정보가 주어진다. 지도에서 1은 집이 위치한 곳이고, 나머지는 0이다.

 

출력

테스트 케이스의 개수만큼 T줄에 T개의 테스트 케이스 각각에 대한 답을 출력한다.
각 줄은 "#x"로 시작하고 공백을 하나 둔 다음 정답을 출력한다. (x는 1부터 시작하는 테스트 케이스의 번호이다)
출력해야 할 정답은 손해를 보지 않으면서 홈방범 서비스를 가장 많은 집들에 제공하는 서비스 영역을 찾았을 때,
그 때의 서비스를 제공 받는 집들의 수이다.

 

 

코드

import sys
sys.stdin = open('2117_input.txt', 'r')

'''
시작점으로부터 집까지의 거리를 미리 계산 >> 집의 위치를 저장할 배열
'''
def find(i, j):
    global maxN

    dis = [0] * (2*N+1)
    for ni, nj in homes:
        # 시작지점으로부터 home까지의 거리를 계산하여 dis에 count
        t = abs(ni-i) + abs(nj-j)
        dis[t] += 1
    # print(dis)

    for k in range(1, 2*N+1):
        numH = sum(dis[:k])
        cost = numH*M - (k*k + (k-1)*(k-1))
        if cost >= 0 and maxN < numH:
            maxN = numH



T = int(input())
# T=1

for test_case in range(1, T+1):
    # 도시의 크기, 하나의 집이 지불할 수 있는 비용
    N, M = map(int, input().split())

    city = [list(map(int, input().split())) for _ in range(N)]
    homes = []

    for i in range(N):
        for j in range(N):
            if city[i][j] == 1:
                homes.append((i, j))

    maxN = 0
    for i in range(N):
        for j in range(N):
            # find에 시작점을보내
            find(i, j)

    print(f'#{test_case} {maxN}')

 

 

 

 

메타세콰이어 길이 보이면 공항에 도착했다는 뜻. 아주아주 자세히 보면 비행기도 날아가는 중~

당분간은 쫌 바빠야 숨이 쉬어질 것 같다. 후하후하

'안바쁘고 누워있기'는 이미 내가 선택할 수 없는 사항이지만,,ㅎ