기본 등산로 조성은 dfs로 4방향에서 갈 수 있다면 방문처리 해주고 가는 방식으로 짰는데

산을 깎는 경우를 잘 모르겠다.

그냥 N만큼 i,j for문 돌리고 그 안에서 K만큼 반복문 돌려서 다 깎아봤어도 시간 초과가 안 났을 것 같은데 풀다보니 이렇게 풀게 됐다.

정리

❗️현재 높이와 다음 높이를 비교했을 때, 작은 경우와 큰 경우를 따로 생각한다.

❗️큰 경우라면 이전에 깎았는지 확인하고 안깎깎 ? 깎 : 안깎처리를 해준다.

❗️다음 높이가 높을 때 깎는 높이는 현재 높이에서 1만 깎으면 된다. 물론 K만큼 깎았을 때 현재 높이보다 낮아야 한다. 이거 이해하는데 오래 걸렸다

❗️방문처리! 깎은 산! 복원이 중요했다. 갔다 왔으면 원래대로 돌려주자.

❗️제일 높은 봉우리만 시작이 됨.

코드

package SWEA;

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

public class Solution_1949_등산로조성 {

    static int N, K, res;
    static int[][] map;
    static boolean[][] v;
    static int[] dr = {-1, 1, 0, 0}, dc = {0, 0, -1, 1};

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer tokens;
        StringBuilder sb = new StringBuilder();
        int T = Integer.parseInt(br.readLine());

        for (int tc = 1; tc <= T; tc++) {
            tokens = new StringTokenizer(br.readLine());
            N = Integer.parseInt(tokens.nextToken());
            K = Integer.parseInt(tokens.nextToken());

            map = new int[N][N];
            v = new boolean[N][N];
            int max = 0;

            for (int i = 0; i < N; i++) {
                tokens = new StringTokenizer(br.readLine());
                for (int j = 0; j < N; j++) {
                    map[i][j] = Integer.parseInt(tokens.nextToken());
                    if (max < map[i][j]) max = map[i][j];
                }
            } // end input

            res = 0;
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    if (map[i][j] == max) {
                        dfs(i, j, 1, true);
                    }
                }
            }
            sb.append("#").append(tc).append(" ").append(res).append("\n");
        } // end test case
        System.out.println(sb);
    }

    private static void dfs(int x, int y, int len, boolean flag) {
        v[x][y] = true;
        for (int d = 0; d < 4; d++) {
            int nx = x + dr[d];
            int ny = y + dc[d];

            // 범위 밖, 방문이면 다음 방향
            if (!isRange(nx, ny) || v[nx][ny])
                continue;

            //다음 높이가 현재 높이보다 작을때
            if (map[nx][ny] < map[x][y]) {
                dfs(nx, ny, len + 1, flag);
            } else {//다음 높이가 현재 높이보다 같거나 크고 깎을 수 있을 때
                if (flag && map[nx][ny] - K < map[x][y]) {
                    int temp = map[nx][ny];
                    v[nx][ny] = true;
                    map[nx][ny] = map[x][y]-1;
                    dfs(nx, ny, len + 1, false);
                    map[nx][ny] = temp;
                    v[nx][ny] = false;
                    flag = true;
                }
            }
        }
        v[x][y] = false;
        // 더이상 갈 수 없으면 거리 갱신
        res = Math.max(res, len);
    }

    private static boolean isRange(int x, int y) {
        if (x < 0 || y < 0 || x >= N || y >= N)
            return false;
        return true;
    }
}

접근 방법

배열에 대한 크기를 2칸 더 확장해줬다. 반복문에서 가장 처음에 map[nx][ny]가 블랙홀인지 확인해야 하는데 ArrayIndexOutOfBoundsException 때문에 테두리를 초기에 999로 설정해주었다.

map = new int[N+2][N+2];

//테두리 설정
for(int i=0; i<N+2; i++) {
    map[0][i] = 999;
    map[i][0] = 999;
    map[N+1][i] = 999;
    map[i][N+1] = 999;
}

블록의 경우엔 block에 대한 변경 좌표를 미리 설정해주고 벽일 경우는 5번 블록과 같이 처리했다

static int[][] block = 
	{{},
	{1, 3, 0, 2},
	{3,0,1,2},
	{2,0,3,1},
	{1,2,3,0},
	{1,0,3,2}};

행의 인덱스는 각 블록에 대한 인덱스이고, 열은 순서대로 상하좌우에 대한 처리이다.

웜홀의 경우는 반복문을 탐색해서 짝 웜홀을 찾으면 다음 위치를 짝 웜홀의 위치로 변경해준다

loop:
for(int i=1; i<=N; i++) {
    for(int j=1; j<=N; j++) {
        if(map[i][j] == map[nx][ny]) {
            if(i==nx && j==ny) continue;
            cx = i; cy = j;
            break loop;
        }
    }
}

코드

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

public class Solution {

	static int N, max, sx, sy;
	static int[][] map;
	static int[][] block = {{},
			{1, 3, 0, 2},
			{3,0,1,2},
			{2,0,3,1},
			{1,2,3,0},
			{1,0,3,2}};
			
	static int[] dr = { -1, 1, 0, 0 }, dc = { 0, 0, -1, 1 };

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer tokens;

		int T = Integer.parseInt(br.readLine());

		for (int tc = 1; tc <= T; tc++) {
			N = Integer.parseInt(br.readLine());
			map = new int[N+2][N+2];
			
			//테두리 설정
			for(int i=0; i<N+2; i++) {
				map[0][i] = 999;
				map[i][0] = 999;
				map[N+1][i] = 999;
				map[i][N+1] = 999;
			}

			//입력
			for (int i = 1; i <= N; i++) {
				tokens = new StringTokenizer(br.readLine());
				for (int j = 1; j <= N; j++) {
					map[i][j] = Integer.parseInt(tokens.nextToken());
				}
			}
			// -1 블랙홀, 1~5 블록, 6~10 웜홀
			// 모든 0의 위치에 대해 4방향으로 가봄
			max = 0;
			for(int i=1; i<=N; i++) {
				for(int j=1; j<=N; j++) {
					if(map[i][j] == 0) {
						for(int d=0; d<4; d++) {
							sx = i; sy = j;
							move(i, j, d);
						}
					}
				}
			}
			System.out.println("#"+tc+" "+max);

		} // end test case
	}

	private static void move(int cx, int cy, int d) {
		// 점수 >> 벽 || 블록
		int score = 0;

		while (true) {
			// 이동 초기 설정
			int nx = cx + dr[d];
			int ny = cy + dc[d];
			
			// 탈출조건 : 시작위치, 블랙홀
			if ((nx == sx && ny == sy) || map[nx][ny] == -1) {
				max = Math.max(max, score);
				return;
			}
			
			// 벽일 경우
			if (map[nx][ny]==999) { //테두리라면
				// 점수 증가
				score++;
				// 방향 전환
				d = block[5][d];
				// 위치 복원
				cx = nx; cy = ny;
				continue;
			}

			// 0일때 위치 갱신
			if (map[nx][ny] == 0) {
				cx = nx; cy = ny;
				continue; //아래 진행 안함
			}
			
			// 블록일 경우
			else if (1 <= map[nx][ny] && map[nx][ny] <= 5) {
				score++; // 점수 증가
				d = block[map[nx][ny]][d];
				cx = nx; // 위치 갱신
				cy = ny;
			}

			// 웜홀일 경우 다음 위치를 짝 웜홀로 변경
			else if (6 <= map[nx][ny] && map[nx][ny]<= 10) {
				loop:
				for(int i=1; i<=N; i++) {
					for(int j=1; j<=N; j++) {
						if(map[i][j] == map[nx][ny]) {
							if(i==nx && j==ny) continue;
							cx = i; cy = j;
							break loop;
						}
					}
				}
			}
		}
	}
}

풀면서 짜증이 많이 났던 문제였다.

같은 방향으로 연속해서 갈 때 x, y에 대한 설정이 헷갈렸다.

접근 방법

뒤에서부터 최대값을 계산한다.

1 1 3 1 2 와 같은 경우를 예시로 들면 

이렇게 된다.

배열을 뒤에서부터 탐색하면서 최대값을 갱신하고, 최대값보다 작은 경우라면 바로 이익을 계산해준다.

또한, N의 크기가 최대 1,000,000이고 각 날의 매매가는 10,000 이하이기 때문에 1,000,000번 최대 매매가를 더해준다 생각하면 10,000,000,000으로 int 자료형 범위를 넘어서기 때문에 합을 계산하는 변수는 long으로 설정했다.

코드

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

public class Solution_1859_백만장자프로젝트 {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer tokens;
		StringBuilder sb = new StringBuilder();

		int T = Integer.parseInt(br.readLine());

		for (int tc = 1; tc <= T; tc++) {
			sb.append("#").append(tc).append(" ");

			int N = Integer.parseInt(br.readLine());
			int[] arr = new int[N];

			int max = 0;
			long profits = 0;

			tokens = new StringTokenizer(br.readLine());
			for (int i = 0; i < N; i++) {
				arr[i] = Integer.parseInt(tokens.nextToken());
			}
			for (int i = N - 1; i >= 0; i--) {
				if(arr[i] > max)
					max = arr[i];
				else
					profits += max - arr[i];
			}
			sb.append(profits).append("\n");
		}
		System.out.println(sb);
	}
}

싸피 코테 치기 전에 풀어봤던 문제인데 다시 풀려니 헷갈려서 더 어렵게 생각했던 것 같다.

수학 들어가면... 🤢

접근 방법

0인 곳을 먼저 클릭해야 한다.

지뢰찾기 게임을 알고 있다면 문제 이해가 쉬워진다.

주어진 예제의 그림을 보면, C를 한번 클릭하면 오른쪽 결과가 나온다.

즉, 주변 지뢰의 수가 0이라면 연속적으로 눌리고, 지뢰의 숫자가 1 이상이면 그 자리에서 멈춘다.

bfs 방식으로 풀이했다.

동작 순서

(1) 맵을 설정한다. 지뢰의 수를 저장할 map 배열과, 방문 체크를 위한 v 배열을 생성한다.

지뢰(*)라면 map에는 -1을, v에는 방문 표시로 1을 체크한다.

(2) 맵에 지뢰의 수를 표시한다. 지뢰가 없는 0인 곳을 클릭하여 8방 탐색 후 지뢰의 개수를 갱신한다.

(3) 0인 곳을 먼저 누른다. 주변에 지뢰가 없는 곳이어야 하고, 방문하지 않은 곳이어야 한다.

(3-1) bfs로 8방 탐색을 한다. 0이면 큐에 넣어주고 나머지 1 이상의 숫자에 대해서는 방문처리만 해준다.

(4) 방문하지 않은 나머지를 눌러준다.

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Queue;

public class Solution_1868_파핑파핑지뢰찾기 {

	static int N, res;
	static int[][] map;
	static int[][] v;

	static int[] dr = { -1, 1, 0, 0, -1, -1, 1, 1 };
	static int[] dc = { 0, 0, -1, 1, -1, 1, -1, 1 };

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

		for (int tc = 1; tc <= T; tc++) {
			N = Integer.parseInt(br.readLine());
			map = new int[N][N]; // 지뢰와 지뢰 수 표시 맵
			v = new int[N][N]; // 클릭한거 체크용
			res = 0;

			String str;
			for (int i = 0; i < N; i++) {
				str = br.readLine();
				for (int j = 0; j < N; j++) {
					if (str.charAt(j) == '*') {
						map[i][j] = -1; // 지뢰면 -1로 표시
						v[i][j] = 1; // 지뢰 있는 곳 방문처리
					}
				}
			} // end input

			// 맵에 지뢰 수 표시. 지뢰:-1 나머지:지뢰수
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < N; j++) {
					if (map[i][j] == 0) {
						// i,j위치에서 8방 지뢰 수 세기
						int cnt = 0;
						for (int d = 0; d < 8; d++) {
							int nx = i + dr[d];
							int ny = j + dc[d];

							if (!isRange(nx, ny))
								continue;
							if (map[nx][ny] != -1)
								continue;
							cnt++;
						}
						map[i][j] = cnt; // 지뢰 수 맵에 갱신
					}
				}
			}

			// 8방이 0인 곳만 누르기
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < N; j++) {
					if (map[i][j] == 0 && v[i][j] == 0) { // 주변에 지뢰가 없고, 방문 x
						click(i, j);
						res++; // 클릭
					}
				}
			}

			// 남은 0인 부분 누르기
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < N; j++) {
					if (v[i][j] == 0) {
						res++;
					}
				}
			}
			sb.append("#").append(tc).append(" ").append(res).append("\n");
		} // end test case
		System.out.println(sb);
	}

	private static void click(int x, int y) {
		// 8방 탐색 해서 0이라면 큐에, 지뢰가 아니고 숫자라면 방문체크만
		Queue<int[]> q = new ArrayDeque<>();
		q.offer(new int[] { x, y });
		v[x][y] = 1;// 방문체크

		while (!q.isEmpty()) {
			int[] cur = q.poll();

			for (int d = 0; d < 8; d++) {
				int nx = cur[0] + dr[d];
				int ny = cur[1] + dc[d];

				// 범위확인
				if (!isRange(nx, ny))
					continue;
				// 지뢰라면 건너뜀
				if (map[nx][ny] == -1)
					continue;
				// 이미 클릭했다면 건너뜀
				if (v[nx][ny] == 1)
					continue;
				// 0이라면 큐에 넣음
				if (map[nx][ny] == 0) {
					q.offer(new int[] { nx, ny });
				}
				// 지뢰수가 표시된 위치 방문처리
				v[nx][ny] = 1;
			}
		}
	}

	private static boolean isRange(int nx, int ny) {
		if (nx >= 0 && ny >= 0 && nx < N && ny < N)
			return true;
		return false;
	}

}

즐겨하는 게임이 지뢰찾기이면서도 0이 연속적으로 눌리는 경우에 대해서 이해하지 못했다.

지뢰찾기 왜 했지?

접근 방법

main

1. 가장 처음에 세로 방향에 대해서 성능 검사를 통과할 수 있는지 확인한다. isTest()
2. 통과하지 못한다면 dfs() 실행

dfs()

• 약품을 투입하지 않는 경우, 약품을 투입하는 경우(A/B)로 나누어 모든 열에 대해 진행한다.
• 마지막 열에 도착했으면 isTest()로 성능 검사를 한다.
• 성능 검사에 통과했다면 약품 최소 투여 횟수를 갱신한다.
• 백트래킹으로 현재 파라미터의 약품 주입 횟수가 갱신된 최소 횟수를 넘었다면 더이상 탐색하지 않는다.

isTest()

• 가장 바깥의 반복문은 모든 열에 대해서 반복한다.
• 검사 통과를 위한 boolean 변수를 선언한다.
• 첫번째 값을 prev 변수에 저장한다
• 모든 행에 대한 반복문 시작
• 이전과 같다면 cnt 증가, 아니라면 cnt를 1로 돌려주고 이전값을 현재 값으로 갱신한다.
• 행을 탐색하면서 cnt가 K에 도달했다면 이 열은 성능검사에서 통과. 다음 열로 진행
• 하나의 열에 대해 모든 행 탐색이 끝났는데 false라면 그 열은 성능검사 통과 못함

import java.util.Scanner;

public class Solution {

	static int D, W, K, res;
	static int[][] map, copy;
	static boolean[] check;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int T = sc.nextInt();
		for (int tc = 1; tc <= T; tc++) {
			res = Integer.MAX_VALUE; // 약품 투입 최소 횟수

			D = sc.nextInt();
			W = sc.nextInt();
			K = sc.nextInt();

			// 0==A, 1==B
			map = new int[D][W];
			copy = new int[D][W];
			for (int i = 0; i < D; i++) {
				for (int j = 0; j < W; j++) {
					map[i][j] = copy[i][j] = sc.nextInt();
				}
			} // end input

			if (isTest()) {
				res = 0;
			} else {
				dfs(0, 0);
			}

			System.out.println("#" + tc + " " + res);
		}
		sc.close();
	}

	private static void dfs(int idx, int cnt) { // 검사 행, 용액 주입 횟수
		// 백트래킹
		if (cnt >= res)
			return;

		// 끝 행까지 dfs를 탔다면 반환
		if (idx == D) {
			// 모든 열이 K를 만족한다면 최소값 갱신
			if (isTest()) {
				res = Math.min(res, cnt);
			}
			return;
		}

		// 한 열에 대해서 idx를 행까지 검사

		// 지금 행을 안 바꾸는 경우
		dfs(idx + 1, cnt);

		// 현재 행을 A로 바꾸는 경우
		for (int j = 0; j < W; j++) {
			copy[idx][j] = 0;
		}
		dfs(idx + 1, cnt + 1);

		// 현재 행을 B로 바꾸는 경우
		for (int j = 0; j < W; j++) {
			copy[idx][j] = 1;
		}
		dfs(idx + 1, cnt + 1);

		// 원래대로 돌려줌
		for (int j = 0; j < W; j++) {
			copy[idx][j] = map[idx][j];
		}

	}

	private static boolean isTest() {
		for (int j = 0; j < W; j++) {
			boolean flag = false;
			int cnt = 1;
			int prev = copy[0][j];
			for (int i = 1; i < D; i++) {
				if (prev == copy[i][j]) {
					cnt++;
				} else {
					cnt = 1;
					prev = copy[i][j];
				}

				if (cnt == K) {
					flag = true;
					break; // 해당 열이 검사에서 통과함
				}
			}
			if (!flag)
				return false; // 한 열이라도 검사에서 통과하지 못하면 false 반환
		}
		return true; // 전부 탐색했을 때 통과된 상태
	}

}

스터디와 역량테스트 때문에 여러번 풀었던 문제였는데 풀때마다 풀이가 조금씩 달라지는 문제였다.

성능검사를 할 때 진행 중 성능검사에 통과하여 다음 열로 진행하는 경우와, 모든 행을 탐색하고 나서 이 행이 통과되는지를 확인하는 부분에서 디버깅이 오래 걸렸다.

또한, 용액을 주입할 때 다른 사람의 코드를 보며 깔끔하게 짜는 코드를 몇가지 확인했다.

• A, B에 대한 값을 final int로 선언하여 직관적으로 변수 관리하기
• 행의 크기만큼 배열 2개를 A, B값으로 전부 변경해두고 arr[idx] = A[idx]와 같이 관리하기

두번째 방법을 보고 나도 저렇게 짤걸!!! 소리없는 절규를 했다. W만큼 반복문을 돌릴 필요가 없을 뿐더러, 배열 값 임시저장해두고 dfs 다 돌았을때 = 연산자로 복귀만 시켜주면 되는 방법... 코드를 짜는 방법에 대해서도 다시 생각해보게 되었다.

문제링크

풀이

T = int(input())
for test in range(1, T+1):
    n, k = map(int, input().split())
    arr = [list(map(int, input().split())) for _ in range(n)]
    # con : 1의 개수 확인, res : k가 들어갈 수 있는 자리 개수
    con = 0
    res = 0
    for i in range(n):
        # 행
        for j in range(n):
            if arr[i][j] == 1:
                con += 1
            if arr[i][j] == 0 or j == n-1:
                if con == k:
                    res += 1
                con = 0
        # 열
        for j in range(n):
            if arr[j][i] == 1:
                con += 1
            if arr[j][i] == 0 or j == n-1:
                if con == k:
                    res += 1
                con = 0
                
    print(f"#{test} {res}")

행과 열을 따로 검사한다.

한 줄씩 읽으면서 1을 만나면 카운트에 추가, 0을 만나거나 한 줄의 끝일 때 카운트와 단어의 길이가 같은지 검사한다.

같으면 결괏값을 증가시킨다. 다음 줄 검사를 위해 카운트를 0으로 초기화한다.

문제링크

풀이

T = int(input())
grade = ["A+", "A0", "A-", "B+", "B0", "B-", "C+", "C0", "C-", "D0"]
for test in range(1, T+1):
    # n : 학생 수, k : 알고 싶은 학생의 번호
    n, k = map(int, input().split())
    # score[] : 학생들의 total 점수를 보관할 리스트
    score = []
    for i in range(n):
        # 중간, 기말, 과제 점수
        mid, fin, work = map(int, input().split())
        total = mid*0.35 + fin*0.45 + work*0.2
        score.append(total)

    # k의 총 점수
    k_score = score[k-1]
    score.sort(reverse=True) # 학점 부여를 위해 내림차순 정렬
    
    rate = n//10
    k_index = score.index(k_score) // rate

    print(f"#{test} {grade[k_index]}")

평점 비율을 이해하는데 시간이 많이 걸렸다.

N명의 학생이 있을 때 N/10명의 학생에게 동일한 평점을 부여한다. 만약 학생수가 30명이면 3명씩 공동 학점이기 때문에 k가 2등이라면 2//3을 했을 때 0이 나오기 때문에 학점 리스트의 0번째 인덱스 학점인 A+를 부여받는다.

문제링크

풀이

T = int(input())
for test in range(1, T+1):
    words = input()
    words2 = words[::-1]
    if words == words2:
        print(f"#{test} 1")
    else:
        print(f"#{test} 0")

[::-1]을 사용하면 리스트의 뒤에서부터 탐색 가능. 파이썬의 장점!

문제링크

풀이

T = int(input())
for test in range(1, T+1):
    n, m = map(int, input().split())
    arr = [0 for _ in range(n)]
    arr = [list(map(int, input().split())) for _ in range(n)]
    res_list = []
    for i in range(n-m+1):
        for j in range(n-m+1):
            res = 0
            for x in range(m):
                for y in range(m):
                    res = res + arr[x+i][y+j]
            res_list.append(res)
    print(f"#{test} {max(res_list)}")

2차원 배열 입력받기 arr = [list(map(int, input().split())) for _ in range(n)]

지금 다시 코드를 보면 4번째 줄을 굳이 써야 하나 싶다.

파리채는 배열의 범위를 넘지 않는 n-m+1만큼 수행

문제링크

풀이

T = int(input())
for test in range(1, T+1):
    print(f"#{test}")
    row = int(input())
    arr = [[0] * row for _ in range(row)]
    for i in range(row):
        for j in range(row):
            if j==0 or i==j:
                arr[i][j] = 1
            else:
                arr[i][j] = arr[i-1][j-1] + arr[i-1][j]
    for i in range(row):
        for j in range(i+1):
            print(arr[i][j], end=' ')
        print()

입력받은 크기만큼 정방향 2차원 배열을 생성한다.

i = 0, i == j는 1로 삽입된다. 그 외에는 왼쪽 위, 오른쪽 위의 요소를 합한 값을 삽입한다.

출력 시 i==j인 부분까지만 출력한다.