PS 일지

문제https://www.acmicpc.net/problem/9328여러 요소들로 이루어진 2차원 격자가 주어진다. 존재하는 요소는 벽$($*$)$, 빈 공간$($.$)$, 문서$($$\$)$, 문$($알파벳 대문자$)$와 각 알파벳에 대응하는 열쇠$($알파벳 소문자$)$들이 있다.상하좌우로 인접한 칸으로만 이동할 수 있고, 경계에 존재하는 빈 공간으로 격자 안과 밖을 오갈 수 있을 때, 얻을 수 있는 문서 개수의 최댓값을 구하는 문제이다. 풀이갈 수 있는 곳들에서 열쇠를 새로 먹어주고, 먹은 열쇠로 열 수 있는 문을 찾아 갈 수 있는 곳을 확장시켜주는 작업을 계속 반복한다.더이상 변화가 생기지 않을 때까지 이를 반복하고, 그 때까지 모은 문서의 수를 출력해주면 된다. import java.util.*;..

문제https://www.acmicpc.net/problem/28060, 1로만 이루어진 길이 $N$인 1-based index 수열 $S$에, $1 \le i \le N$을 골라서 아래 두 가지 연산을 할 수 있다.1. $S[i] = S[i] \oplus 1$2. $S[1] = S[1] \oplus 1, \cdots, S[i] = S[i] \oplus 1$$ \oplus $는 exclusive or를 의미한다.모든 원소를 $0$으로 만드는 데 필요한 최소 연산 횟수를 구하는 문제이다.풀이$1$인 원소를 $0$으로 만드는 방법에는 아래 것들이 존재한다.1. 모든 원소 $1$에 대해, 1번 연산 수행하기2. 특정 구간 $[l,r]$의 원소가 모두 $1$일 때, 2번 연산을 각각 $i = l-1, i=r$로..

문제https://www.acmicpc.net/problem/147160과 1로만 이루어진 2차원 격자가 주어진다.1이 격자 상에서 인접한 8방향으로 연결되어있다면 연결 요소 전체를 한 글자로 볼 때,총 연결 요소의 수를 구하는 문제이다. 풀이격자를 순회하며 1을 만날 때마다 BFS로 연결 요소를 모두 방문처리한 후 글자 수를 올려주었다. import java.util.*;import java.io.*;class Node{ int x; int y; Node(int x, int y){ this.x = x; this.y = y; }}public class Main { static StringTokenizer st; static int nextInt()..

문제https://www.acmicpc.net/problem/17471정점이 $N$개이고, 정점에 양의 정수 가중치가 있는 그래프가 주어진다. 이 그래프의 정점들을 서로 겹치지 않게 두 집합으로 분할하여 각 집합 내의 정점들끼리 연결되도록 하였을 때, 두 집합의 가중치 합 차이의 최솟값을 구해야 한다. 풀이재귀 + 비트마스킹을 이용해 가능한 두 집합을 완탐으로 구해주었다.두 집합이 정해지면, 분리 집합으로 집합 내의 연결 여부를 확인하고 답을 구해주었다. #include #include #include #include using namespace std;int r[10]{}, s[10]{}, N;int f(int x) { return x == r[x] ? x : r[x] = f(r[x]); }int an..

문제https://www.acmicpc.net/problem/12928정수 $N$과 $S$가 주어지면, 정점의 개수가 $N$개이며 길이가 $2$인 단순 경로의 수가 $S$개인 트리를 만들 수 있는지 판별하는 문제다. 두 경로가 서로 방향만 다르고 지나는 점이 동일하면 같은 경로이다. 풀이정점의 개수가 $n$개이고 길이가 $2$인 단순 경로의 수가 $s$개인 트리가 있다고 가정하자.이 트리에서 차수가 $k$인 정점에 새 정점을 이어붙이면, 단순 경로의 수는 $s+k$가 된다.구체적으로, 정점의 수가 $n$이고 길이가 $2$인 단순 경로의 수가 $s$이며, 차수가 $k$인 정점이 존재하는지 여부는 배낭으로 쉽게 알 수 있다. 위 정의대로 $d[n][k][s]$를 정의하면, $d[n][k][s] = 1$일 때..