greentea31's Note

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5V4A46AdIDFAWu&& 

풀이 과정

문제의 조건에 맞게 주어진 벌통을 선택할 때, 선택한 벌통내에서 채취할 수 있는 가치의 최대값을 구하는 문제이다.

일꾼이 벌통을 선택하는 경우를 중복 순열의 경우의 수를 만들어 구하였고, 각 벌통의 칸에서 꿀을 퍼갈지 안퍼갈지를 부분집합의 경우의 수를 만들어 구하였다.

N, M이 크지 않은 수로 주어지므로 완전 탐색으로 풀 수 있음을 추측할 수 있다. 로직을 세우고 시간복잡도를 계산해도 문제에서 주어진 시간을 초과하지 않음을 알 수 있다. 설명은 코드에 주석으로 달아놓았다.

소스 코드

def perm(index):  # 첫번째 벌꿀통의 r, c 두번째 벌꿀통의 r, c를 중복순열로 생성
    if index == 4:
        check()  # 값을 구하러 간다
        return

    for i in range(N):
        numbers.append(i)  # 이번 수를 중복 순열에 넣고
        perm(index+1)  # 다음 index의 수를 고르러 간다
        numbers.pop()  # 이번 수를 중복 순열에 넣지 않고 이번 index에 넣을 다음 수를 찾으러 간다


def check():
    global answer, max1
    a, b, c, d = numbers[0], numbers[1], numbers[2], numbers[3]
    if b > N-M or d > N-M:  # M칸 크기의 벌꿀 통을 가로줄에 넣을 수 없는 경우 진행하지 않는다
        return
    selected = [[False for _ in range(N)] for _ in range(N)]  # 벌꿀통이 놓인 곳을 표시
    subset_selected = [[False for _ in range(N)] for _ in range(N)]  # 벌꿀통 안에서 벌꿀을 퍼갈 공간 표시
    for i in range(M):
        selected[a][b+i] = True  # 벌꿀통을 놓았다고 표시한다
    max1 = 0
    subset(a, b, 0, subset_selected)  # 벌꿀통 안에서 퍼간 벌꿀의 양이 C를 넘지 않으면서 최대 가치를 지니는 경우가 언제인지
    # 부분집합으로 모든 경우를 만들어서 판단한다
    max2 = max1

    for i in range(M):
        if selected[c][d+i]:  # 2번째 벌꿀 통을 놓는데 1번째 벌꿀 통이랑 겹치면 진행하지 않는다
            return
        selected[c][d+i] = True
    max1 = 0
    subset(c, d, 0, subset_selected)  # 2번째 벌꿀 통 안에서 1번째 벌꿀통 부분집합 만들기에서 했던 것과 동일 행위 진행

    answer = max(answer, max1 + max2)  # 정답 갱신


def subset(i, j, index, subset_selected):  # 부분집합 경우의 수 생성 코드
    global max1
    if index == M:  # 모든 벌꿀통의 칸에 대해 진행했으면
        temp = 0
        values = 0
        for k in range(M):
            if subset_selected[i][j+k]:  # 선택된 칸의
                temp += board[i][j+k]  # 양의 누적을 저장하고
                values += board[i][j+k]**2  # 가치의 누적을 저장한다
        if temp > C:  # 양이 C를 넘었으면 담을 수 없으므로 진행하지 않는다
            return
        max1 = max(max1, values)  # 양이 C를 넘지 않았다면 가치 누적값의 최대를 갱신한다
        return

    subset_selected[i][j + index] = True  # 벌꿀통의 특정 칸을 고르는 경우
    subset(i, j, index+1, subset_selected)  # 재귀 진행
    subset_selected[i][j+index] = False  # 벌꿀통의 특정 칸을 고르지 않는 경우
    subset(i, j, index + 1, subset_selected)  # 재귀 진행


T = int(input())

for tc in range(1, T+1):
    max1 = 0
    N, M, C = map(int, input().split())
    board = [list(map(int, input().split())) for _ in range(N)]  # 2차원 배열 1줄로 받는 코드
    answer = 0  # 정답을 저장할 변수
    numbers = []  # 중복순열을 생성할 코드
    perm(0)  # 중복순열 재귀
    print(f"#{tc} {answer}")  # 정답 출력

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV140YnqAIECFAYD 

풀이 과정

완전 이진 트리가 주어질 때 중위 순회의 결과값을 출력하는 문제이다.

완전 이진 트리의 루트를 1번 노드라고 하면, 배열로 트리를 표현할 수 있다.

i번째 노드의 왼쪽 자식 노드는 2i, 오른쪽 자식 노드는 2i+1, 부모 노드는 i/2로 저장하면 배열로 트리의 표현이 가능하다.

전위 순회는 자신 -> 왼쪽 자식 -> 오른쪽 자식

중위 순회는 왼쪽 자식 -> 자신 -> 오른쪽 자식

후위 순회는 왼쪽 자식 -> 오른쪽 자식 -> 자신

순으로 순회한다. 보통 전, 중, 후위 순회를 구현할 때 재귀를 이용하는데, 재귀문의 위치를 조금만 바꿔주면 3가지의 순회를 쉽게 구현할 수 있다.

소스 코드

import sys
input = sys.stdin.readline


def dfs(cur):
    if cur > n: # 트리 크기보다 현재 방문점이 커지면 종료
        return
    dfs(cur*2) # 왼쪽 자식 노드 방문
    print(temp[cur][1], end="") # 현재 노드 출력
    dfs(cur*2+1) # 오른쪽 자식 노드 방문
    #왼쪽 -> 현재 -> 오른쪽 순으로 방문하는 중위 순회이며 위의 3줄의 코드의 위치에 따라
    #전위, 중위, 후위 순회가 결정된다


for tc in range(1, 11):
    n = int(input())
    temp = [0] # 0번 노드는 안쓸거니까 비워둔다

    for i in range(n):
        temp.append(list(map(str, input().split()))) # 입력

    print(f"#{tc} ", end="")
    dfs(1) # 1번 노드부터 재귀에 들어간다
    print()

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AXRSXf_a9qsDFAXS 

풀이 과정

N과 M이 주어질 때, M의 이진수 표현의 마지막 비트 N자리가 모두 1인지를 판별하는 문제이다.

N자리가 모두 1로 차있는 이진수 T를 고려해보자. M과 T를 OR 연산을 시행했을때, M의 마지막 비트 N자리중에 0인 비트는 1로 바뀌게 되어 M은 다른 숫자로 변하게 된다. 따라서 N자리가 모두 1일때만 OR 연산을 시행 후에도 M의 값이 변하지 않게 됨을 이용해 비트마스킹으로 문제를 해결할 수 있다.

소스 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Solution {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());

        for (int tc = 1; tc <= T; tc++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int N = Integer.parseInt(st.nextToken());
            int M = Integer.parseInt(st.nextToken());
            if ((M | ((1 << N)) - 1) == M) { // M과, 마지막 N비트에 1을 채운 수를 OR 연산한 값이 M이면, M의 마지막 N비트는 모두 1이다. 
                // 마지막 N비트에 1이 아닌 수가 있다면, OR 연산 이후에 1로 바뀌고, 기존의 M과 다른 수가 된다.
                System.out.printf("#%d %s\n", tc, "ON"); // 따라서 ON이다.
            } else {
                System.out.printf("#%d %s\n", tc, "OFF"); // 아니면 OFF다.
            }
        } // end of testcase
    } // end of main
} // end of class

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV18_yw6I9MCFAZN 

풀이 과정

N의 배수 번호인 양을 세면서 모든 숫자를 다 볼려면 양을 몇번 봐야 하는지 구하는 문제이다.

문제 그대로 모든 숫자를 다 볼 때 까지 계속 양을 센 횟수에 N을 더해주면 된다. 숫자를 모두 봤는지 판별할 때 어떤 숫자가 나왔는지를 저장하는 사이즈 10의 배열을 선언할 수도 있겠지만 비트마스킹을 사용해서 좀 더 빠르게 판단할 수 있다.

소스 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Solution {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());

        for (int tc = 1; tc <= T; tc++) {
            int N = Integer.parseInt(br.readLine()); // 문제의 입력 N
            int visited = 0; // 현재까지 본 숫자를 bit로 표현한 수, 2-4-5를 봤다면 0000110100 (2)
            int target = (1 << 10) - 1; // 1111111111 (2) -> visited == target이면 모든 숫자 관찰
            int answer = 0; // 양을 몇 번 세었는지 저장한다

            while (visited != target) { // 모든 숫자를 볼 때 까지 반복한다
                answer += N; // 양을 N번 더 센다
                char[] ch = String.valueOf(answer).toCharArray(); // 숫자를 문자열로 변환 후 문자 배열로 저장한다
                for (char c : ch) {
                    int num = c - '0'; // 문자 배열의 각 문자를 숫자 값으로 받는다
                    visited = visited | (1 << num); // 현재까지 본 숫자를 비트마스킹으로 표시해준다
                }
            }
            System.out.printf("#%d %d\n", tc, answer);
        } // end of testcase
    } // end of main
} // end of class

https://swexpertacademy.com/main/code/problem/problemDetail.do?problemLevel=2&contestProbId=AV5PobmqAPoDFAUq&categoryId=AV5PobmqAPoDFAUq&categoryType=CODE&problemTitle=&orderBy=FIRST_REG_DATETIME&selectCodeLang=ALL&select-1=2&pageSize=10&pageIndex=2 

풀이 과정

NxN 차원 배열에 시계방향으로 바깥쪽부터 안쪽까지 숫자를 1씩 늘려가면서 채우는 문제이다.

배열에 채워야 할 수가 NxN으로 정해져 있으므로 이미 채워진 블록, 배열의 끝을 만나면 방향을 진행 방향의 오른쪽으로 바꿔가며 배열에 수를 N^2번 채우면 된다.

처음 풀 때 while문을 이용해서 좀 지저분하게 짰는데 그 코드도 맨 아래에 남겨놓았다.

소스 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Solution {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());
        // 동 남 서 북
        int[] dy = {0, 1, 0, -1};
        int[] dx = {1, 0, -1, 0};

        for (int tc = 1; tc <= T; tc++) {
            int N = Integer.parseInt(br.readLine());
            int[][] board = new int[N][N];
            int y = 0; int x = 0;
            int num = 1;
            int direction = 0;

            for (int i = 0; i < N*N; i++) {
                board[y][x] = num++;
                int ny = y + dy[direction];
                int nx = x + dx[direction];

                if (ny < 0 || ny > N-1 || nx < 0 || nx > N-1 || board[ny][nx] != 0) {
                    direction++;
                    if (direction == 4) {
                        direction = 0;
                    }
                }

                y += dy[direction];
                x += dx[direction];
            }

            System.out.printf("#%d\n", tc);

            for (int i = 0; i < N; i++) {
                for (int j : board[i]) {
                    System.out.print(j+" ");
                }
                System.out.println();
            }
        }
    }
}

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Solution {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());

        for (int tc = 1; tc <= T; tc++) {
            int N = Integer.parseInt(br.readLine());
            int[][] board = new int[N][N];

            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    board[i][j] = 0;
                }
            }

            int direction = 0;
            int r = 0; int c = 0;
            int num = 1;
            while (board[r][c] == 0) {
                board[r][c] = num++;
                if (direction == 0 ) {
                    if (c+1 < N && board[r][c+1] == 0) {
                        c++;
                    } else {
                        if (r+1 < N && board[r+1][c] == 0) {
                            direction++;
                        } else {
                            break;
                        }
                    }
                }

                if (direction == 1) {
                    if (r+1 < N && board[r+1][c] == 0) {
                        r++;
                    } else {
                        if (c-1 >= 0 && board[r][c-1] == 0) {
                            direction++;
                        } else {
                            break;
                        }
                    }
                }

                if (direction == 2) {
                    if (c-1 >= 0 && board[r][c-1] == 0) {
                        c--;
                    } else {
                        if (r-1 >= 0 && board[r-1][c] == 0) {
                            direction++;
                        } else {
                            break;
                        }
                    }
                }

                if (direction == 3) {
                    if (r-1 >= 0 && board[r-1][c] == 0) {
                        r--;
                    } else {
                        if (c+1 < N && board[r][c+1] == 0) {
                            direction = 0;
                            c++;
                        } else {
                            break;
                        }
                    }
                }
            }

            System.out.printf("#%d\n", tc);
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    System.out.print(board[i][j] + " ");
                }
                System.out.println();
            }
        }
    }
}

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV134DPqAA8CFAYh&categoryId=AV134DPqAA8CFAYh&categoryType=CODE&problemTitle=&orderBy=INQUERY_COUNT&selectCodeLang=ALL&select-1=&pageSize=10&pageIndex=1 

풀이 과정

왼쪽, 오른쪽으로 2칸까지 다른 건물에 의해 뷰가 가려지지 않을 때, 조망권이 확보되었다고 하는데 여러 건물의 높이가 주어졌을 때 조망권이 확보된 세대의 수를 구하는 문제이다.

각 건물에 대해 왼쪽으로 2칸, 오른쪽으로 2칸에 있는 모든 건물의 높이를 확인 후,  현재 건물 - 근처 가장 높은 건물의 높이를 정답에 더해주면 된다. 현재 건물이 더 낮아서 조망권이 확보되는 세대가 없다면, 아무 것도 더해주지 않으면 된다.

소스 코드

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int T, garo, num;
    int number = 1;
    T = 10;
    while(T--) {
        int answer = 0;
        cin >> garo;
        vector<int> V(garo);
        for (int i = 0; i < garo; i++) {
            cin >> num;
            V[i] = num;
        }
        for (int i = 2; i < garo - 2; i++) {
            int temp = max({V[i-2], V[i-1], V[i+1], V[i+2]});
            if (V[i] > temp) answer += (V[i] - temp);
        }

        cout << '#' << number++ << ' ' << answer << '\n';
    }

    return 0;
}