By_Me

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]);

	}
}

난이도: 골드 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;
}

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

해당 문제는 dp와 hash를 적용하여 문제를 해결하였다,

처음에, dp만을 활용하여 재귀함수 호출을 통해서 문제를 제출했으나, 시간 초과가 발생하였다. 아무래도 n <= 10^ 12, p, q <= 10^9이다보니, memorization을 활용하지 않아서 그런 것 같다.

* 해당 문제는 Top-down 방식으로 dp를 해결하다보니 memorization이 필요하다.

따라서 map STL 라이브러리를 사용하여 해결하는데, 해당 문제에서 dp의 순서는 크게 상관없기때문에 상대적으로 더 간단한 unordered_map을 활용한다. 또한 배열로 선언하기에는 n이 너무 크므로, map을 활용하여 필요한 값들만 따로 저장해두므로 훨씬 편리하다.

또한, 

A[0] = 1

A[i] = A[i/p] + A[j/q] 이므로 다음과 같이 코드를 작성하였다.

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

long long n, p, q;
long long res = 0;
unordered_map<long long, long long> m;

long long solution(long long x)
{
    if (x == 0)
        return 1;

    if (m[x] != 0)
    {
        return m[x];
    }
    else
    {
        return m[x] = solution(x / p) + solution(x / q);
    }
}

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

    cin >> n >> p >> q;

    m[0] = 1;
    cout << solution(n);

    return 0;
}

bool visited[10] : 자신과 중복되는 값을 제거하기 위해 사용

int xx : 중복순열을 제거하기 위해 이전에 입력한 값을 저장하고, 현재 받으려는 값과 비교하여 값이 같으면 중복 수열이므로 넘어가준다.

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

int n, m;
vector<int> v;
int res[10];
bool visited[10];

void dfs(int cnt)
{
    if (cnt == m)
    {
        for (int i = 0; i < m; i++)
        {
            cout << res[i] << " ";
        }
        cout << '\n';
        return;
    }
    else
    {
        int xx = 0;
        for (int i = 0; i < v.size(); i++)
        {
            if (visited[i] || v[i] == xx)
            {
                continue;
            }

            visited[i] = true;
            res[cnt] = v[i];
            xx = v[i];
            dfs(cnt + 1);
            visited[i] = false;
        }
    }
}
int main(int argc, char const *argv[])
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n >> m;

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

        v.push_back(x);
    }

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

    dfs(0);

    return 0;
}

참고자료: https://yabmoons.tistory.com/536

사용되는 알고리즘 : dp

* 특별한 경우를 잘 확인해야한다. => 이전 타일을 이용해서 쌓아가는 걸 제외하고 특별한 모양

* n이 홀수일 경우는 애초에 고려하지 않는다. => 3 * odd의 경우 넓이는 홀수값이 되는데 2*1 또는 1*2로 채우는 경우는 값이 무조건 짝수가 나와야 한다.

#include <iostream>
using namespace std;

int dp[31];

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

    int n;
    cin >> n;

    dp[0] = 1;
    dp[2] = 3;

    if (n % 2 == 1)
    {
        cout << 0;
        return 0;
    }

    for (int i = 4; i <= n; i += 2)
    {
        dp[i] = dp[i - 2] * dp[2];

        for (int j = i - 4; j >= 0; j -= 2)
        {
            dp[i] += 2 * dp[j];
        }
    }

    cout << dp[n];

    return 0;
}

참고자료에 올린 블로그에서 설명을 자세하게 해주어서 이해하는데 많은 도움이 되었다.