By_Me

https://www.acmicpc.net/problem/2504

다시 풀 문제

문제를 처음 봤을 땐 딱봐도 Stack을 사용해야하는 문제라고 생각했지만, 괄호간의 연산에 대해서 덧셈과 곱셈을 어떻게 처리해야할지 고민했던 문제. 다른 사람의 풀이를 참고하여 풀었다.

각각의 case에 대해 경우의 수를 나눠서 backTracking 같이 풀이를 진행하였다. 나는 괄호가 끝날 때, 연산을 진행하려고 했는데, 작성자는 시작하는 괄호가 나왔을 때, 임시로 값을 담아놓고, 만약 괄호가 정상적으로 종료된다면 해당 값을 최종 결과에 저장하는 방식을 사용했다.

따라서 만약 시작하는 괄호가 여러 개 나온다면 계속 tmp에 괄호에 해당하는 연산을 곱해주고, 이후 하나의 괄호가 닫힐 때마다, tmp를 해당 값만큼 나눠준다.

import java.util.*;
import java.io.*;

public class BOJ_G5_2504_괄호의값 {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		String str = br.readLine();

		Stack<Character> stk = new Stack<>();
		int res = 0;
		int val = 1;

		for (int i = 0; i < str.length(); i++) {
			char curr = str.charAt(i);

			if (curr == '(') {
				stk.push(curr);
				val *= 2;
			} else if (curr == '[') {
				stk.push(curr);
				val *= 3;
			} else if (curr == ')') {
				if (stk.isEmpty() || stk.peek() != '(') {
					res = 0;
					break;
				} else if (str.charAt(i - 1) == '(') {
					res += val;
				}
				stk.pop();
				val /= 2;
			} else if (str.charAt(i) == ']'){
				if (stk.isEmpty() || stk.peek() != '[') {
					res = 0;
					break;
				} else if (str.charAt(i - 1) == '[') {
					res += val;
				}
				stk.pop();
				val /= 3;
			}
		}

		if (!stk.isEmpty()) res = 0;

		sb.append(res);
		System.out.println(sb);
	}
}

같이 풀면 좋은 문제

https://www.acmicpc.net/problem/24042

다익스트라 알고리즘

- 최단 경로를 위해 사용

- 현재 코드는 우선순위 큐를 이용

- 가중치 값들이 모두 0보다 커야 한다.(음수일 경우에는 안됨)

import java.util.*;
import java.io.*;

public class DijkstraPqMain {
	public static void main(String[] args) throws Exception {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		// 인접 행렬로 만듦.
		int[][] g = new int[N][N];
		// MST에 속하면 true.
		boolean[] v = new boolean[N];
		int[] dist = new int[N];

		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				g[i][j] = sc.nextInt();
			}
			dist[i] = Integer.MAX_VALUE;
		}

		PriorityQueue<int[]> pq = new PriorityQueue<>((o1, o2) ->
			Integer.compare(o1[1], o2[1])
		);
		// 0번 정점부터 MST에 시작
		dist[0] = 0;

		pq.offer(new int[] {0, dist[0]});

		while (!pq.isEmpty()) {
			int[] cur = pq.poll();
			int minVertex = cur[0];
			int min = cur[1];
			if (v[minVertex]) continue; // 싸이클 방지
			
			v[minVertex] = true;
			
			if (minVertex == N-1) break;
			for (int j = 0; j < N; j++) {
				if (!v[j] && g[minVertex][j] != 0 && dist[j] > min + g[minVertex][j]) {
					dist[j] = min + g[minVertex][j];
					pq.offer(new int[] {j, dist[j]});
				}
			}
				
		}
		System.out.println(dist[N-1]);
		sc.close();
	}
}

https://www.acmicpc.net/problem/2877

2025년 엠로 상반기 코테와 유사한 문제였다.
규칙을 잘보면, 이진수처럼 표현이 가능해진다. 0 : 4, 4 : 7

첫 번째 이진수 자리를 지워주면 각각 대응되서 숫자가 표현되는 것을 확인할 수 있다.

package _250320;

import java.util.*;
import java.io.*;

/**
 *packageName    : _250320
 * fileName       : BOJ_G5_2877_4와7
 * author         : moongi
 * date           : 3/21/25
 * description    :
 */
public class BOJ_G5_2877_4와7 {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		String s = Integer.toBinaryString(Integer.parseInt(br.readLine()) + 1).replace('0', '4').replace('1', '7');

		StringBuilder sb = new StringBuilder();
		for (int i = 1; i < s.length(); i++) {
			sb.append(s.charAt(i));
		}
		System.out.println(sb);
	}
}

https://www.acmicpc.net/problem/2169

해당 문제는 2025년 상반기 엠로 코딩테스트 문제와 유사하였다.

처음엔 별 생각 없이, bfs로 접근하였는데, 이후에 dp로 푸는 문제라는 것을 깨달았다. 그러나, 최댓값을 구하는 과정에서 풀이 방식이 생각나지 않았다.

package _250320;

import java.util.*;
import java.io.*;

/**
 *packageName    : _250320
 * fileName       : BOJ_G2_2169_로봇조종하기
 * author         : moongi
 * date           : 3/21/25
 * description    :
 */
public class BOJ_G2_2169_로봇조종하기 {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());

		int[][] arr = new int[N][M];
		int[][] dp = new int[N][M];
		int[][] tmp = new int[2][M];

		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < M; j++) {
				arr[i][j] = Integer.parseInt(st.nextToken());
			}
		}

		dp[0][0] = arr[0][0];
		for (int i = 1; i < M; i++) {
			dp[0][i] = dp[0][i - 1] + arr[0][i];
		}

		for (int i = 1; i < N; i++) {

			// 왼쪽에서 오른쪽으로 오는 것
			tmp[0][0] = dp[i - 1][0] + arr[i][0];
			for (int j = 1; j < M; j++) {
				tmp[0][j] = Math.max(tmp[0][j - 1], dp[i - 1][j]) + arr[i][j];
			}

			// 오른쪽에서 왼쪽으로 오는 것
			tmp[1][M - 1] = dp[i - 1][M - 1] + arr[i][M - 1];
			for (int j = M - 2; j >= 0; j--) {
				tmp[1][j] = Math.max(dp[i - 1][j], tmp[1][j + 1]) + arr[i][j];
			}

			for (int j = 0; j < M; j++) {
				dp[i][j] = Math.max(tmp[0][j], tmp[1][j]);
			}

		}

		System.out.println(dp[N-1][M-1]);

	}
}

0. 해당 글을 쓰게 된 배경

1. 필드의 구분

1. 클래스 변수(static variable)
2. 인스턴스 변수(instance variable)
3. 지역 변수(local variable)

class Car {

    static int modelOutput; // 클래스 변수
    String modelName;       // 인스턴스 변수
    
    void method() {
        int something = 10; // 지역 변수
    }
}

class Field {
    static int classVar = 10; // 클래스 변수 선언
    int instanceVar = 20; // 인스턴스 변수 선언
}

public class FieldEx2 {
    public static void main(String[] args) {

        int var = 30; // 지역 변수 선언
        System.out.println("var = " + var); // 지역 변수 참조

        Field myField1 = new Field(); // 인스턴스 생성
        Field myField2 = new Field(); // 인스턴스 생성

        System.out.println("Field.classVar = " + Field.classVar); // 클래스 변수 참조
        System.out.println("myField1 = " + myField1.classVar);
        System.out.println("myField2.classVar = " + myField2.classVar);

        myField1.classVar = 100; // 클래스 변수의 값을 변경

        System.out.println("Field.classVar = " + Field.classVar); // 클래스 변수 참조
        System.out.println("myField1 = " + myField1.classVar);
        System.out.println("myField2 = " + myField2.classVar);

        myField1.instanceVar = 200;

        System.out.println("myField1 = " + myField1.instanceVar); // 인스턴스 변수 참조
        System.out.println("myField2 = " + myField2.instanceVar);

    }
}

2. 메소드의 구분

1. 클래스 메소드(static method)
2. 인스턴스 메소드(instance method)

class Method {
    int a = 10, b = 20;
//    static int add() {return a + b;} // 다음과 같이 static 메소드는 메소드 내부에서 인스턴스 변수를 사용할 수 없다.
    int add() {return a + b;}
    static int add(int x, int y) {return x + y;}
}

public class TcpMethod2 {
    public static void main(String[] args) {
        System.out.println("Method.add(20, 30) = " + Method.add(20, 30));
        Method myMethod = new Method();
        System.out.println("myMethod.add() = " + myMethod.add());

    }
}

3. 초기화 블록

1. 명시적 초기화
2. 생성자를 이용한 초기화
3. 초기화 블록을 이용한 초기화
   1. 인스턴스 초기화 블록
      1. 인스턴스 초기화 블록은 단순히 중괄호({})만을 사용하여 정의
      2. 인스턴스 초기화 블록은 생성자와 마찬가지로 인스턴스가 생성될 때마다 실행
      3. 인스턴스 초기화 블록이 생성자보다 먼저 실행
      4. 여러 개의 생성자가 있으면 모든 생성자에서 공통으로 수행되어야 할 코드를 인스턴스 초기화 블록에 포함하여 코드의 중복을 막을 수 있다. 

class Car {
    private String modelName;
    private int modelYear;
    private String color;
    private int maxSpeed;
    private int currentSpeed;

    { // 인스턴스 초기화 블록 : 단순히 중괄호({})만을 사용, 인스턴스가 생성될 때마다 실행, 인스턴스 초기화 블록이 생성자보다 먼저 실행
        this.currentSpeed = 0;
    }

    Car() {}

    public Car(String modelName, int modelYear, String color, int maxSpeed) {
        this.modelName = modelName;
        this.modelYear = modelYear;
        this.color = color;
        this.maxSpeed = maxSpeed;
    }

    public int getSpeed() {
        return currentSpeed;
    }
}
public class TcpMethod3 {
    public static void main(String[] args) {
        Car myCar = new Car();
        System.out.println("myCar.getSpeed() = " + myCar.getSpeed());
    }
}

2. 클래스 초기화 블록:

1. 인스턴스 초기화 블록에 static 키워드를 추가하여 정의할 수 있다.
2. 클래스가 처음으로 메모리에 로딩될 때 단 한 번만 실행됩니다.

class InitBlock {
    static int classVar; // 클래스 변수
    int instanceVar; // 인스턴스 변수

    static { // 클래스 초기화 블록을 이용한 초기화
        classVar = 10;
    }
}
public class Member04 {
    public static void main(String[] args) {
        System.out.println("InitBlock.classVar = " + InitBlock.classVar); // 클래스 변수에 접근
    }
}

4. 필드의 초기화 순서

1. 클래스 변수: 기본값 -> 명시적 초기화 -> 클래스 초기화 블록
2. 인스턴스 변수: 기본값 -> 명시적 초기화 -> 인스턴스 초기화 블록 -> 생성자

class InitBlock {
    static int classVar = 10; // 클래스 변수의 명시적 초기화
    int instanceVar = 10; // 인스턴스 변수의 명시적 초기화

    static { // 클래스 초기화 블록을 이용한 초기화
        classVar = 20;
    }
    { // 인스턴스 초기화 블록을 이용한 초기화
        instanceVar = 20;
    }

    public InitBlock() {
        this.instanceVar = 30; // 생성자를 이용한 초기화
    }
}
public class Member04 {
    public static void main(String[] args) {
        System.out.println("InitBlock.classVar = " + InitBlock.classVar); // 클래스 변수에 접근
        InitBlock myInit = new InitBlock();
        System.out.println("myInit.instanceVar = " + myInit.instanceVar);
    }
}

난이도: 골드 3

알고리즘 : 시뮬레이션

배열을 90도씩 회전하는 부분에 구현을 어떻게 해야할지 감이 잡히지 않아서 조금 해맸다.

#include <iostream>
#include <cstring>
using namespace std;

int n, m, k;
int r, c;
int pan[41][41] = {
    0,
};
int sticker[11][11] = {
    0,
};
void findSpace(int L);
void patchSpace(int st_x, int st_y);
void rotation(int L);
void input()
{
    cin >> n >> m >> k;

    for (int i = 0; i < k; i++)
    {
        cin >> r >> c;

        memset(sticker, 0, sizeof(sticker) / sizeof(int));

        for (int j = 0; j < r; j++)
            for (int t = 0; t < c; t++)
                cin >> sticker[j][t];
        findSpace(0);
    }
}

void findSpace(int L)
{
    if (L == 4)
        return;

    for (int i = 0; i <= n - r; i++)
    {
        for (int j = 0; j <= m - c; j++)
        {
            bool endFlag = false;
            for (int t = 0; t < r; t++)
            {
                for (int s = 0; s < c; s++)
                {
                    // 스티커 붙일 자리가 채워진 경우
                    if (sticker[t][s] == 1)
                    {
                        if (sticker[t][s] == pan[i + t][j + s])
                        {
                            endFlag = true;
                            break;
                        }
                    }
                }
                if (endFlag)
                    break;
            }
            if (!endFlag)
            {
                // 스티커를 붙일 수 있다면
                patchSpace(i, j);
                return;
            }
        }
    }

    rotation(L);
}

void patchSpace(int st_x, int st_y)
{
    for (int i = 0; i < r; i++)
        for (int j = 0; j < c; j++)
            if (pan[i + st_x][j + st_y] != 1)
                pan[i + st_x][j + st_y] = sticker[i][j];
}

void rotation(int L)
{
    int tmp[11][11] = {
        0,
    };

    for (int i = 0; i < r; i++)
        for (int j = 0; j < c; j++)
            tmp[i][j] = sticker[i][j];

    memset(sticker, 0, sizeof(sticker) / sizeof(int));
    for (int i = 0; i < r; i++)
        for (int j = 0; j < c; j++)
            sticker[j][r - i - 1] = tmp[i][j];
    swap(r, c);
    findSpace(L + 1);
}

int solution()
{
    int res = 0;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            if (pan[i][j] == 1)
                res++;
    return res;
}
int main(int argc, char const *argv[])
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    input();
    cout << solution();

    return 0;
}

0. 과정

난이도 : 골드 4
풀이 방법 : DFS + BackTracking
해설:
기존에는 backtracking을 위해서 move에서 이동했던 것 만큼 다시 되돌려주었는데 
6 6
1 0 0 0 0 0
0 1 0 0 0 0
0 0 1 5 0 0
0 0 5 1 0 0
0 0 0 0 1 0
0 0 0 0 0 1
답 : 2

다음 input값에서 무한루프가 돌았다. 따라서 다른 사람들의 풀이를 참고하니 굳이 moveBackTracking()를 통해 되돌려주는 대신 tmp 배열을 이용해 기존 방문했던 visited 배열을 저장했다가 다시 되돌려주는 방식을 이용하였다.

1. 첫 번째 풀이

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

int n, m;
int pan[9][9];
int visited[9][9] = {
    0,
};
int dx[] = {-1, 1, 0, 0};
int dy[] = {0, 0, -1, 1};

vector<pair<int, int>> cctv;

int res = INT_MAX;

void input()
{
    cin >> n >> m;

    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            cin >> pan[i][j];

            if (pan[i][j] != 0 && pan[i][j] != 6)
            {
                cctv.push_back({i, j});
            }
            if (pan[i][j] != 0)
            {
                visited[i][j]++;
            }
        }
    }
}

void move(int x, int y, int dir)
{
    while (true)
    {
        int nx = x + dx[dir];
        int ny = y + dy[dir];

        if (nx >= 0 && nx < n && ny >= 0 && ny < m && pan[nx][ny] != 6)
        {
            visited[nx][ny]++;
            x = nx;
            y = ny;
        }
        else
        {
            break;
        }
    }
}

void moveBackTracking(int x, int y, int dir)
{
    while (true)
    {
        int nx = x + dx[dir];
        int ny = y + dy[dir];

        if (nx >= 0 && nx < n && ny >= 0 && ny < m && pan[nx][ny] != 6)
        {
            visited[nx][ny]--;
            x = nx;
            y = ny;
        }
        else
        {
            break;
        }
    }
}

void DFS(int L)
{

    if (L == cctv.size())
    {
        int ans = 0;
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < m; j++)
            {
                if (!visited[i][j])
                {
                    ans++;
                }
            }
        }

        res = min(res, ans);

        return;
    }

    for (int i = L; i < cctv.size(); i++)
    {
        int x = cctv[i].first;
        int y = cctv[i].second;

        if (pan[x][y] == 1)
        {
            for (int j = 0; j < 4; j++)
            {
                move(x, y, j);
                DFS(L + 1);
                moveBackTracking(x, y, j);
            }
        }
        else if (pan[x][y] == 2)
        {
            // 상하
            move(x, y, 0);
            move(x, y, 1);
            DFS(L + 1);
            moveBackTracking(x, y, 0);
            moveBackTracking(x, y, 1);

            // 좌우
            move(x, y, 2);
            move(x, y, 3);
            DFS(L + 1);
            moveBackTracking(x, y, 2);
            moveBackTracking(x, y, 3);
        }
        else if (pan[x][y] == 3)
        {
            // 상
            move(x, y, 0);
            for (int j = 2; j < 4; j++)
            {
                move(x, y, j);
                DFS(L + 1);
                moveBackTracking(x, y, j);
            }
            moveBackTracking(x, y, 0);

            // 하
            move(x, y, 1);
            for (int j = 2; j < 4; j++)
            {
                move(x, y, j);
                DFS(L + 1);
                moveBackTracking(x, y, j);
            }
            moveBackTracking(x, y, 1);
        }
        else if (pan[x][y] == 4)
        {
            for (int j = 0; j < 4; j++)
            {
                move(x, y, j);
            }
            for (int j = 0; j < 4; j++)
            {
                moveBackTracking(x, y, j);
                DFS(L + 1);
                move(x, y, j);
            }
            for (int j = 0; j < 4; j++)
            {
                moveBackTracking(x, y, j);
            }
        }
        else if (pan[x][y] == 5)
        {
            for (int j = 0; j < 4; j++)
            {
                move(x, y, j);
            }
            DFS(L + 1);
            for (int j = 0; j < 4; j++)
            {
                moveBackTracking(x, y, j);
            }
        }
    }
}

int main(int argc, char const *argv[])
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    input();
    DFS(0);

    cout << res;

    return 0;
}

2. 정답 풀이

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

int dx[] = {-1, 0, 1, 0}; // 상,우,하,좌
int dy[] = {0, 1, 0, -1};
int n, m; // 세로, 가로
int pan[9][9];
int visited[9][9] = {
    0,
};
vector<pair<int, int>> cctv;
int res = INT_MAX;

void input()
{
    cin >> n >> m;

    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
        {
            cin >> pan[i][j];

            if (pan[i][j] != 0)
            {
                visited[i][j] += 1;
                if (pan[i][j] != 6)
                    cctv.push_back({i, j});
            }
        }
}

void move(int x, int y, int dir)
{
    dir %= 4;
    while (true)
    {
        int nx = x + dx[dir];
        int ny = y + dy[dir];

        if (nx >= 0 && nx < n && ny >= 0 && ny < m && pan[nx][ny] != 6)
        {
            visited[nx][ny] += 1;
            x = nx;
            y = ny;
        }
        else
            break;
    }
}

void DFS(int L)
{
    if (L == cctv.size())
    {
        int ans = 0;
        for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++)
                if (visited[i][j] == 0)
                    ans++;
        res = min(res, ans);

        return;
    }

    int tmp[9][9];
    for (int k = 0; k < 4; k++)
    {

        for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++)
                tmp[i][j] = visited[i][j];

        int x = cctv[L].first;
        int y = cctv[L].second;

        if (pan[x][y] == 1)
        {
            move(x, y, k);
        }
        else if (pan[x][y] == 2)
        {
            move(x, y, k);
            move(x, y, k + 2);
        }
        else if (pan[x][y] == 3)
        {
            move(x, y, k);
            move(x, y, k + 1);
        }
        else if (pan[x][y] == 4)
        {
            move(x, y, k);
            move(x, y, k + 1);
            move(x, y, k + 2);
        }
        else if (pan[x][y] == 5)
        {
            move(x, y, k);
            move(x, y, k + 1);
            move(x, y, k + 2);
            move(x, y, k + 3);
        }

        DFS(L + 1);

        for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++)
                visited[i][j] = tmp[i][j];
    }
}
int main(int argc, char const *argv[])
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    input();
    DFS(0);
    cout << res;

    return 0;
}

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

int n;
vector<vector<int>> pan;
int dx[] = {-1, 1, 0, 0};
int dy[] = {0, 0, -1, 1};
int res = 0;

extern vector<vector<int>> move_up(vector<vector<int>> v);
extern vector<vector<int>> move_down(vector<vector<int>> v);
extern vector<vector<int>> move_right(vector<vector<int>> v);
extern vector<vector<int>> move_left(vector<vector<int>> v);

void dfs(int L, vector<vector<int>> v)
{
    if (L == 5)
    {
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                res = max(res, v[i][j]);
        return;
    }

    dfs(L + 1, move_up(v));
    dfs(L + 1, move_down(v));
    dfs(L + 1, move_right(v));
    dfs(L + 1, move_left(v));
}

vector<vector<int>> move_up(vector<vector<int>> v) // 0
{
    vector<vector<bool>> visited(n, vector<bool>(n, false));

    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            if (v[i][j] == 0)
                continue;

            int x = i;
            int y = j;
            while (1)
            {
                int nx = x + dx[0];
                int ny = y + dy[0];

                // 경계값을 넘는 경우
                if (nx < 0 || nx >= n || ny < 0 || ny >= n || visited[nx][ny])
                    break;

                // 값이 들어있는 경우
                if (v[nx][ny] != 0)
                {
                    // 이동할 값과 현재 값이 같은 경우
                    if (v[nx][ny] == v[x][y])
                    {
                        v[nx][ny] *= 2;
                        v[x][y] = 0;
                        visited[nx][ny] = true;
                    }
                    break;
                }
                // 이동할 칸이 빈 값인 경우
                else
                {
                    v[nx][ny] = v[x][y];
                    v[x][y] = 0;
                    x = nx;
                    y = ny;
                }
            }
        }
    }

    return v;
}

vector<vector<int>> move_down(vector<vector<int>> v) // 1
{
    vector<vector<bool>> visited(n, vector<bool>(n, false));

    for (int i = n - 1; i >= 0; i--)
    {
        for (int j = 0; j < n; j++)
        {
            if (v[i][j] == 0)
                continue;

            int x = i;
            int y = j;
            while (1)
            {

                int nx = x + dx[1];
                int ny = y + dy[1];

                // 경계값을 넘는 경우
                if (nx < 0 || nx >= n || ny < 0 || ny >= n || visited[nx][ny])
                    break;

                if (v[nx][ny] != 0)
                {
                    if (v[nx][ny] == v[x][y])
                    {
                        v[nx][ny] *= 2;
                        v[x][y] = 0;
                        visited[nx][ny] = true;
                    }
                    break;
                }
                else
                {
                    // 이동할 칸이 빈 값인 경우
                    v[nx][ny] = v[x][y];
                    v[x][y] = 0;
                    x = nx;
                    y = ny;
                }
            }
        }
    }

    return v;
}

vector<vector<int>> move_right(vector<vector<int>> v) // 3
{
    vector<vector<bool>> visited(n, vector<bool>(n, false));

    for (int j = n - 1; j >= 0; j--)
    {
        for (int i = 0; i < n; i++)
        {
            if (v[i][j] == 0)
                continue;

            int x = i;
            int y = j;
            while (1)
            {
                int nx = x + dx[3];
                int ny = y + dy[3];

                // 경계값을 넘는 경우
                if (nx < 0 || nx >= n || ny < 0 || ny >= n || visited[nx][ny])
                    break;

                if (v[nx][ny] != 0)
                {
                    if (v[nx][ny] == v[x][y])
                    {
                        v[nx][ny] *= 2;
                        v[x][y] = 0;
                        visited[nx][ny] = true;
                    }
                    break;
                }
                // 이동할 칸이 빈 값인 경우
                else
                {
                    v[nx][ny] = v[x][y];
                    v[x][y] = 0;
                    x = nx;
                    y = ny;
                }
            }
        }
    }

    return v;
}

vector<vector<int>> move_left(vector<vector<int>> v)
{
    vector<vector<bool>> visited(n, vector<bool>(n, false));

    for (int j = 0; j < n; j++)
    {
        for (int i = 0; i < n; i++)
        {
            if (v[i][j] == 0)
                continue;

            int x = i;
            int y = j;
            while (1)
            {
                int nx = x + dx[2];
                int ny = y + dy[2];

                // 경계값을 넘는 경우
                if (nx < 0 || nx >= n || ny < 0 || ny >= n || visited[nx][ny])
                    break;

                if (v[nx][ny] != 0)
                {
                    if (v[nx][ny] == v[x][y])
                    {
                        v[nx][ny] *= 2;
                        v[x][y] = 0;
                        visited[nx][ny] = true;
                    }
                    break;
                }
                // 이동할 칸이 빈 값인 경우
                else
                {
                    v[nx][ny] = v[x][y];
                    v[x][y] = 0;
                    x = nx;
                    y = ny;
                }
            }
        }
    }
    return v;
}

int main(int argc, char const *argv[])
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n;

    pan.resize(n, vector<int>(n, 0));

    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            cin >> pan[i][j];

    dfs(0, pan);

    cout << res;

    return 0;
}

난이도: G4

문제풀이 : stack 이용

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

int main(int argc, char const *argv[])
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;

    stack<pair<int, int>> stk;
    vector<int> res(n, -1);

    int x;
    for (int i = 0; i < n; i++)
    {
        cin >> x;

        while (!stk.empty() && stk.top().second < x)
        {
            res[stk.top().first] = x;
            stk.pop();
        }

        stk.push({i, x});
    }

    for (auto v : res)
        cout << v << " ";

    return 0;
}

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

int n;
long long m;
vector<long long> v;

long long res = INT_MAX;
void selectedNum(int start, int end)
{
    while (start <= end && end < n)
    {
        if (v[end] - v[start] == m)
        {
            res = m;
            return;
        }
        else if (v[end] - v[start] > m)
        {
            res = min(res, v[end] - v[start]);
            start++;
        }
        else
        {
            end++;
        }
    }
}

int main(int argc, char const *argv[])
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n >> m;

    long long x;
    for (int i = 0; i < n; i++)
    {
        cin >> x;
        v.push_back(x);
    }

    sort(v.begin(), v.end());

    selectedNum(0, 0);

    cout << res;

    return 0;
}