• A번 - 선물
• B번 - 운명
• C번 - 해킹
• D번 - 스터디 카페
• E번 - 육각형 순회

양말을 $2X$개 구매하기 위한 최소 비용을 구하는 문제입니다. 문제에 따르면 양말은 항상 연속된 이틀에 걸쳐서 사야하고, 매일 $X$개씩 구매하려고 해야 합니다.

$i$일에 양말을 $X$개 구매했다면, $i+1$일에도 양말을 $X$개 구매해야 합니다. 이때 양말을 구매하는 총 비용은 $A_i \times X + A_{ i+1 } \times X$ 입니다.

가능한 모든 $i$ ($1 \le i \le N-1$) 중에서 최소가 되는 $i$를 찾고, 그때 비용을 계산하면 됩니다.

import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int x = sc.nextInt();
        int[] a = new int[n];
        for (int i=0; i<n; i++) {
            a[i] = sc.nextInt();
        }
        int ans = a[0]+a[1];
        for (int i=0; i<n-1; i++) {
            int cur = a[i] + a[i+1];
            if (ans > cur) {
                ans = cur;
            }
        }
        System.out.println(ans*x);
    }
}

n, x = map(int, input().split())
a = list(map(int, input().split()))
ans = a[0]+a[1]
for i in range(1, n-1):
    cur = a[i] + a[i+1]
    if ans > cur:
        ans = cur
print(ans*x)

왼발에 신을 수 있는 양말이 $X$개 있고, 오른발에 신을 수 있는 양말도 $X$개 있습니다. 양말의 색은 $K$가지 존재합니다.

왼발 양말 하나와 오른발 양말 하나를 신고 나가려고 하는데, 두 양말의 색은 달라야 합니다. 이때 양말을 신을 수 있는 방법의 수를 구하는 문제입니다.

각각의 왼발에 신을 수 있는 양말마다 색이 다른 오른발 양말의 개수를 세어주는 방식으로 해결 할 수 있습니다.

import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int x = sc.nextInt();
        int k = sc.nextInt();
        int[] left = new int[x];
        int[] right = new int[x];
        for (int i=0; i<x; i++) {
            left[i] = sc.nextInt();
        }
        for (int i=0; i<x; i++) {
            right[i] = sc.nextInt();
        }
        long ans = 0;
        for (int i=0; i<x; i++) {
            for (int j=0; j<x; j++) {
                if (left[i] != right[j]) {
                    ans += 1;
                }
            }
        }
        System.out.println(ans);
    }
}

x, k = map(int, input().split())
a = list(map(int, input().split()))
left = a[:x]
right = a[x:]
ans = 0
for i in range(x):
    for j in range(x):
        if left[i] != right[j]:
            ans += 1
print(ans)

소스 2와 같이 구현하면 방법의 수를 구할 수 있습니다. 이 소스의 시간 복잡도는 $O(X^2)$ 입니다. 하지만, 문제의 $X$ 제한은 $X \le 100\,000$이기 때문에, 를 받게 됩니다.

색이 $u$인 왼쪽 양말의 개수를 $l$, 오른쪽 양말의 개수를 $r$이라고 합시다. 이때 색이 $u$인 왼쪽 양말을 하나 신었을때 신을 수 있는 오른쪽 양말의 개수는 $X - r$개 입니다. 색이 $j$인 오른쪽 양말의 개수를 미리 구해놓았다면, 양말을 하나씩 검사하지 않고도 개수를 구할 수 있게 됩니다.

소스 3은 이 아이디어를 이용해 구현한 소스입니다. cnt[j]에는 색이 j인 오른쪽 양말의 개수가 저장되어 있습니다.

import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int x = sc.nextInt();
        int k = sc.nextInt();
        int[] left = new int[x];
        int[] right = new int[x];
        int[] cnt = new int[k+1];
        for (int i=0; i<x; i++) {
            left[i] = sc.nextInt();
        }
        for (int i=0; i<x; i++) {
            right[i] = sc.nextInt();
            cnt[right[i]] += 1;
        }
        long ans = 0;
        for (int i=0; i<x; i++) {
            ans += x - cnt[left[i]];
        }
        System.out.println(ans);
    }
}

x, k = map(int, input().split())
a = list(map(int, input().split()))
left = a[:x]
right = a[x:]
cnt = [0] * (k+1)
for r in right:
    cnt[r] += 1
ans = 0
for i in range(x):
    ans += x - cnt[left[i]]
print(ans)

$N$개의 컴퓨터와 $M$개의 통신망이 있고, $i$번 컴퓨터를 해킹하면 1분 뒤부터 매분 $A_i$의 돈을 가져올 수 있습니다. $X$개의 컴퓨터를 해킹해야 합니다.

$B_1 , B_2 , \dots , B_Y$번 컴퓨터에는 보안 시스템이 설치될 예정입니다. 이것이 설치된 컴퓨터에서는 돈을 가져올 수 없고, 설치되고 1분 뒤에는 통신망으로 직접 연결된 모든 컴퓨터에 보안 시스템이 자동으로 설치됩니다.

문제의 목표는 얼마나 많은 돈을 얻을 수 있을지 구하는 것입니다.

많은 돈을 얻으려면 해킹한 컴퓨터에 보안 시스템이 최대한 늦게 설치되어야 합니다. 이를 위해 각 컴퓨터에 언제 보안 시스템이 설치되는지 구해야합니다. 컴퓨터와 통신망은 그래프로 모델링할 수 있습니다. 한 컴퓨터에 보안 시스템이 설치되고, 직접 연결된 다른 컴퓨터에 보안 시스템이 설치되는데는 1분이 걸립니다. 이것은 간선의 가중치가 $1$인 것으로 볼 수 있습니다. 따라서, 한 컴퓨터에 보안 시스템이 설치되는 시간은 BFS 알고리즘으로 구할 수 있습니다.

BFS 알고리즘을 이용해 각 컴퓨터에 보안 시스템이 설치되는 시간을 구합니다. $i$번 컴퓨터에 보안 시스템이 설치되는 시간을 $T_i$라고 합시다. 그럼 이 컴퓨터에서 얻을 수 있는 돈의 양은 $T_i \times A_i$ 입니다. 여기서 가장 큰 $X$개의 합이 문제의 정답이 됩니다.

만약, 그래프가 연결되어 있지 않다면, 보안 시스템이 설치되지 않는 컴퓨터가 존재합니다. 이 경우 무한히 많은 돈을 얻을 수 있습니다. 하지만, 보안 시스템이 설치되지 않은 컴퓨터가 있다고 하더라도 항상 돈을 무한히 얻을 수 있는 것은 아닙니다. 문제의 $A_i$ 조건은 $0 \le A_i \le 500\,000$이기 때문에, $A_i$가 $0$인 경우가 존재할 수 있습니다. 보안 시스템이 설치되지 않은 컴퓨터에서 매분 $0$만큼의 돈을 가져올 수 있다면, 무한히 많은 돈을 얻는 경우는 아닙니다.

import java.util.*;
import java.io.*;
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] line = br.readLine().split(" ");
        int n = Integer.parseInt(line[0]);
        int m = Integer.parseInt(line[1]);
        int x = Integer.parseInt(line[2]);
        int y = Integer.parseInt(line[3]);
        int[] a = new int[n];
        line = br.readLine().split(" ");
        for (int i=0; i<n; i++) {
            a[i] = Integer.parseInt(line[i]);
        }
        ArrayList<Integer>[] g = new ArrayList[n];
        for (int i=0; i<n; i++) {
            g[i] = new ArrayList<>();
        }
        for (int i=0; i<m; i++) {
            line = br.readLine().split(" ");
            int u = Integer.parseInt(line[0])-1;
            int v = Integer.parseInt(line[1])-1;
            g[u].add(v);
            g[v].add(u);
        }
        int[] b = new int[y];
        line = br.readLine().split(" ");
        for (int i=0; i<y; i++) {
            b[i] = Integer.parseInt(line[i]);
        }
        long[] dist = new long[n];
        for (int i=0; i<n; i++) {
            dist[i] = -1;
        }
        Queue<Integer> q = new LinkedList<>();
        for (int i=0; i<y; i++) {
            int v = b[i]-1;
            dist[v] = 0;
            q.add(v);
        }
        while (!q.isEmpty()) {
            int u = q.remove();
            for (int v : g[u]) {
                if (dist[v] == -1) {
                    dist[v] = dist[u] + 1;
                    q.add(v);
                }
            }
        }
        boolean inf = false;
        for (int i=0; i<n; i++) {
            dist[i] = dist[i] * a[i];
            if (dist[i] < 0) {
                inf = true;
            }
        }
        if (inf) {
            System.out.println(-1);
        } else {
            Arrays.sort(dist);
            long sum = 0;
            for (int i=0; i<x; i++) {
                sum += dist[n-i-1];
            }
            System.out.println(sum);
        }
    }
}

from collections import deque
import sys
input = sys.stdin.readline
n, m, x, y = map(int, input().split())
a = list(map(int, input().split()))
g = [[] for _ in range(n)]
for _ in range(m):
    u, v = map(int, input().split())
    u -= 1
    v -= 1
    g[u].append(v)
    g[v].append(u)
b = list(map(int, input().split()))
dist = [-1] * n
q = deque()
for v in b:
    v -= 1
    dist[v] = 0
    q.append(v)
while q:
    u = q.popleft()
    for v in g[u]:
        if dist[v] == -1:
            dist[v] = dist[u] + 1
            q.append(v)
inf = False
for i in range(n):
    dist[i] = dist[i] * a[i]
    if dist[i] < 0:
        inf = True
if inf:
    print(-1)
else:
    dist = sorted(dist)[::-1]
    dist = dist[:x]
    print(sum(dist))

$i$일에 $k$명이 방문했을때 그 날 얻을 수 있는 수익의 최댓값은 $A_i$에서 가장 큰 값 $k$개입니다. 최솟값도 비슷한 방식으로 구할 수 있습니다.

$i$일에 방문한 사람의 수가 $V_i$명이라면, 위의 방법을 이용해서 문제의 정답을 구할 수 있습니다. 이렇게 해결하려면 크기가 $10^9$인 배열이 필요합니다. 그 다음, 각각의 사람 $j$마다 $S_j$부터 $E_j$까지 순회하면서 $V$의 값을 $1$ 증가시켜야 합니다. 공간도 너무 많이 필요하고, 시간도 너무 많이 걸립니다. 다른 방법을 생각해봅시다.

스터디 카페에서 사람이 변하는 날짜는 최대 $2M$개가 있습니다. 사람이 변하지 않는 기간이 있다면, 이때 얻을 수 있는 수익은 한 번에 구할 수 있습니다. 예를 들어, $2$, $3$, $4$일에 사람이 $1$명 왔고, $5$일에 사람이 $2$명 왔다면, $2$, $3$, $4$에서 얻을 수 있는 수익의 최솟값과 최댓값은 변하지 않습니다. 이 아이디어를 이용해 사람이 변하지 않는 기간을 한 번에 처리할 수 있습니다.

$A_i$에서 가장 큰 값 $k$개의 합과 작은 값 $k$개의 합은 누적 합을 이용해 $O(1)$에 구할 수 있습니다.

import java.util.*;
import java.io.*;
class Event implements Comparable<Event> {
    int time, what;
    Event(int time, int what) {
        this.time = time;
        this.what = what;
    }
    public int compareTo(Event that) {
        if (this.time < that.time) {
            return -1;
        } else if (this.time == that.time) {
            if (this.what < that.what) {
                return -1;
            } else if (this.what == that.what) {
                return 0;
            } else {
                return 1;
            }
        } else {
            return 1;
        }
    }
    public boolean equals(Event that) {
        return this.time == that.time && this.what == that.what;
    }
}
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] line = br.readLine().split(" ");
        int n = Integer.parseInt(line[0]);
        int m = Integer.parseInt(line[1]);
        ArrayList<Integer> a_min = new ArrayList<>();
        ArrayList<Integer> a_max = new ArrayList<>();
        line = br.readLine().split(" ");
        for (int i=0; i<n; i++) {
            int x = Integer.parseInt(line[i]);
            a_min.add(x);
            a_max.add(x);
        }
        Collections.sort(a_min);
        Collections.sort(a_max);
        Collections.reverse(a_max);
        a_min.add(0, 0);
        a_max.add(0, 0);
        long[] pre_min = new long[n+1];
        long[] pre_max = new long[n+1];
        for (int i=1; i<=n; i++) {
            pre_min[i] = pre_min[i-1] + a_min.get(i);
            pre_max[i] = pre_max[i-1] + a_max.get(i);
        }
        ArrayList<Event> a = new ArrayList<>();
        for (int i=0; i<m; i++) {
            line = br.readLine().split(" ");
            int u = Integer.parseInt(line[0]);
            int v = Integer.parseInt(line[1]);
            a.add(new Event(u, 1));
            a.add(new Event(v+1, 0));
        }
        Collections.sort(a);

        long ans_min = 0;
        long ans_max = 0;

        int cnt = 0;

        int last = 0;

        m *= 2;

        for (int i=0; i<m; i++) {
            int t = a.get(i).time;
            int what = a.get(i).what;
            int cur = Math.min(cnt, n);
            ans_min += pre_min[cur] * (t - last);
            ans_max += pre_max[cur] * (t - last);
            if (what == 0) {
                cnt -= 1;
            } else {
                cnt += 1;
            }
            last = t;
        }
        System.out.println(ans_min + " " + ans_max);
    }
}

import sys
input = sys.stdin.readline
n, m = map(int, input().split())
a_min = list(map(int, input().split()))
a_min = sorted(a_min)
a_max = a_min[::-1]
a_min = [0] + a_min
a_max = [0] + a_max
pre_min = [0] * (n+1)
pre_max = [0] * (n+1)
for i in range(1, n+1):
    pre_min[i] = pre_min[i-1] + a_min[i]
    pre_max[i] = pre_max[i-1] + a_max[i]

a = []
for _ in range(m):
    u, v = map(int, input().split())
    a.append((u, 1))
    a.append((v+1, 0))

a.sort()

ans_min = 0
ans_max = 0

cnt = 0

last = 0

m *= 2

for i in range(m):
    t, what = a[i]
    cur = min(cnt, n)
    ans_min += pre_min[cur] * (t - last)
    ans_max += pre_max[cur] * (t - last)
    if what == 0:
        cnt -= 1
    else:
        cnt += 1
    last = t
print(ans_min,ans_max)

a_min은 입력으로 주어진 $A$가 오름차순으로, a_max는 내림차순으로 저장되어 있습니다. 이 값을 이용해 누적 합 pre_min과 pre_max를 구할 수 있습니다.

a에 들어가는 값은 time과 what입니다. time은 사람이 변하는 시점이고, what이 0이면 사람이 감소, 1이면 증가하는 것입니다. 어떤 사람이 스터디 카페를 u일부터 v일까지 이용했다면, 사람의 수가 변할 수 있는 시점은 u일과 v+1일이기 때문에, v는 1을 더해서 넣습니다.

cnt에는 스터디 카페에 있는 사람의 수, last에는 마지막으로 수익을 구한 날짜가 저장되어 있습니다.

이를 이용해 사람이 변하는 날마다 얻을 수 있는 수익을 한 번에 구할 수 있습니다.

문제에 설명에 나와있는 건축물을 크기가 $N$인 지도로 표현하겠습니다.

임의의 위치 $(x, y)$에 대한 정답을 구할 수 있다면, 나머지 위치에 대해서도 답을 항상 구할 수 있습니다. 그 이유는 모든 방을 정확히 한 번씩 돌아본 후 다시 원래의 위치로 돌아와야 하기 때문입니다.

$(1, 1)$은 모든 크기 $N$에 대해서 존재하는 위치이기 때문에, 각각의 크기 $N$마다 어떻게 방법을 구할 수 있는지 알아보겠습니다.

그림 1. $N = 5$

여기서 $(1, 1)$, $(2, 2)$, $\dots$, $(N, N)$까지 칸을 빨간색으로 색칠해봅시다.

그림 2

빨간색 칸을 제외한 칸 중에서 가장 외곽에 있는 칸을 파란색으로 색칠해봅시다.

그림 3

그 다음 외곽에 있는 칸은 초록색으로 색칠해봅시다.

그림 4

이런 식으로 외곽의 색을 모두 다르게 칠할 수 있습니다.

그림 5

$(1, 1)$에서 시작해서 각각의 외곽을 모두 방문하고, $(N, N)$에 방문한 다음, 여기서 빨간색 칸을 이용해서 $(1, 1)$로 돌아오는 경로를 모든 $N$에 대해서 만들 수 있습니다.

그림 6

import java.util.*;
class Pair {
    int x, y;
    Pair(int x, int y) {
        this.x = x;
        this.y = y;
    }
}
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int sx = sc.nextInt();
        int sy = sc.nextInt();
        ArrayList<Integer> limits = new ArrayList<>();
        limits.add(0);
        for (int i=0; i<n; i++) {
            limits.add(n+i);
        }
        for (int i=n-2; i>=0; i--) {
            limits.add(n+i);
        }
        int m = 2*n;
        boolean[][] check = new boolean[m][m];
        for (int i=1; i<=n; i++) {
            check[i][i] = true;
        }

        int[] dx = {0, 1, 1, 0, -1, -1};
        int[] dy1 = {1, 1, 0, -1, -1, 0};
        int[] dy2 = {1, 0, -1, -1, 0, 1};
        String[] dc = {"D", "C", "Z", "A", "Q", "E"};
        ArrayList<Pair> path = new ArrayList<>();
        path.add(new Pair(1, 1));
        ArrayList<String> direction = new ArrayList<>();

        int x = 1;
        int y = 1;

        for (int level=1; level<n; level++) {
            int k = 0;
            int dk = 1;
            if (level % 2 == 0) {
                k = 2;
                dk = -1;
            }
            for (int i=0; i<6; i++) {
                while (true) {
                    int nx = x+dx[k];
                    int ny = y+dy1[k];
                    if (dx[k] != 0) {
                        if ((dx[k] == 1 && nx <= n) || (dx[k] == -1 && nx < n)) {
                            ny = y+dy1[k];
                        } else {
                            ny = y+dy2[k];
                        }
                    }

                    if (1 <= nx && nx < m && 1 <= ny && ny <= limits.get(nx) && check[nx][ny] == false) {
                        path.add(new Pair(nx, ny));
                        direction.add(dc[k]);
                        check[nx][ny] = true;
                        x = nx;
                        y = ny;
                    } else {
                        break;
                    }
                }

                k += dk;
                if (k == -1) {
                    k = 5;
                }
            }
            if (level != n-1) {
                x = x+dx[1];
                y = y+dy1[1];
                path.add(new Pair(x, y));
                direction.add(dc[1]);
                check[x][y] = true;
            }
        }

        if (n % 2 == 1) {
            direction.add("Z");
        } else {
            direction.add("D");
        }

        for (int i=n; i>1; i--) {
            path.add(new Pair(i, i));
            direction.add("Q");
        }

        int index = 0;

        for (int i=0; i<path.size(); i++) {
            if (path.get(i).x == sx && path.get(i).y == sy) {
                index = i;
                break;
            }
        }

        StringBuilder sb = new StringBuilder();
        for (int i=index; i<path.size(); i++) {
            sb.append(direction.get(i));
        }
        for (int i=0; i<index; i++) {
            sb.append(direction.get(i));
        }
        System.out.println(sb);
    }
}

n, sx, sy = map(int, input().split())
limits = [0]
for i in range(n):
    limits.append(n+i)
for i in range(n-2, -1, -1):
    limits.append(n+i)
m = 2*n
check = [[False]*m for _ in range(m)]
for i in range(1, n+1):
    check[i][i] = True


dx = [0, 1, 1, 0, -1, -1]
dy1 = [1, 1, 0, -1, -1, 0]
dy2 = [1, 0, -1, -1, 0, 1]
dc = ['D', 'C', 'Z', 'A', 'Q', 'E']

path = [(1, 1)]
direction = []

x = 1
y = 1

for level in range(1, n):
    if level % 2 == 1:
        k = 0
        dk = 1
    else:
        k = 2
        dk = -1
    for _ in range(6):
        while True:
            nx = x+dx[k]
            ny = y+dy1[k]
            if dx[k] != 0:
                if (dx[k] == 1 and nx <= n) or (dx[k] == -1 and nx < n):
                    ny = y+dy1[k]
                else:
                    ny = y+dy2[k]

            if 1 <= nx < m and 1 <= ny <= limits[nx] and check[nx][ny] == False:
                path.append((nx, ny))
                direction.append(dc[k])
                check[nx][ny] = True
                x = nx
                y = ny
            else:
                break

        k += dk
        if k == -1:
            k = 5

    if level != n-1:
        x = x + dx[1]
        y = y + dy1[1]
        path.append((x, y))
        direction.append(dc[1])
        check[x][y] = True

if n % 2 == 1:
    direction.append('Z')
else:
    direction.append('D')

for i in range(n, 1, -1):
    path.append((i, i))
    direction.append('Q')

index = 0
for i in range(len(path)):
    if path[i] == (sx, sy):
        index = i
        break

ans = direction[index:] + direction[:index]
print(''.join(ans))

• limits[r]: r번 행의 마지막 열 번호가 limits[r]임
• check[r][c]: (r, c)를 방문한 적이 있으면 true, 아니면 false
• dc[k]: k번 방향을 나타내는 대문자
• dx[k]: dc[k]번 방향으로 이동했을때 행의 변화
• dy1[k], dy2[k]: dc[k]번 방향으로 이동했을때 열의 변화
  • 열의 변화는 n번 행을 기준으로 다르기 때문에 두 가지 사용
• path: 방문한 칸을 순서대로 저장
• direction: 방문한 방법을 순서대로 저장