블로그 언저리인 무언가

문제 : 20114 미아 노트 20114번: 미아 노트 첫째 줄에 원래 문자열의 길이 N, 세로로 번진 글자의 개수 H, 가로로 번진 글자의 개수 W가 주어진다. (1 ≤ N ≤ 100, 1 ≤ H ≤ 10, 1 ≤ W ≤ 10) 둘째 줄부터 H개의 줄에 걸쳐 N × W 길이의 문자열이 www.acmicpc.net N길이의 문자열이 H*W크기만 큼 번지고 지워졌을 때, 원래 문자열을 복구해서 출력하는 문제이다. 현재의 문자가 원래 문자열의 어느 위치인지 찾아서 갱신해주고 찾지 못한 위치의 문자는 '?'을 출력해주면 된다 Code #include #define ll long long using namespace std; int main(){ ios::sync_with_stdio(0); cin.tie(0);..

문제 : 4781 사탕 가게 4781번: 사탕 가게 각 테스트 케이스의 첫째 줄에는 가게에 있는 사탕 종류의 수 n과 상근이가 가지고 있는 돈의 양 m이 주어진다. (1 ≤ n ≤ 5,000, 0.01 ≤ m ≤ 100.00) m은 항상 소수점 둘째자리까지 주어진다. 다음 n개 www.acmicpc.net 사탕가게에 있는 모든 사탕의 가격과 칼로리가 주어질 때, 보유한 금액 내에서 칼로리합이 가장 크도록 사탕을 사는 문제이다. 같은 사탕을 여러 개 살 수 있기 때문에 DP 알고리즘을 사용해서 배열을 채우면 된다. 입력으로 주어지는 실수를 정수로 바꿀 때 오차가 날 수 있으므로 반올림을 위해서 0.5를 더한 후 바꾼다. Code #include #define ll long long using namespa..

문제 : 2110 공유기 설치 2110번: 공유기 설치 첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (1 ≤ xi ≤ 1,000,000,000)가 � www.acmicpc.net 집의 위치와 설치하는 공유기의 개수가 주어졌을 때, 가장 인접한 두 공유기 사이의 거리를 최대로 만들었을 때 그 거리를 출력하는 문제이다. 최적으로 되도록 공유기를 설치했을 때 첫 번째 집에 공유기를 설치하지 않았다면 맨 왼쪽 집의 공유기를 첫 번째로 옮길 수 있으므로 첫 번째 집에 공유기를 설치하는 최적해가 언제나 존재한다. 따라서 첫 번째 집에 공유기를 설치했다고 가정한 후..

문제 : 18116 로봇 조립 18116번: 로봇 조립 성규는 로봇을 조립해야 한다. 상자 안에는 여러 로봇의 부품들이 섞여 있다. 그런데 어떤 부품이 어느 로봇의 부품인지 표시가 되어있지 않다. 호재는 전자과라서 두 부품을 보면 같은 로봇의 � www.acmicpc.net 서로 다른 부품이 2개가 주어지고 두 부품이 같은 로봇의 부품이란 것을 알려줄 때, 어떤 로봇의 현재까지 알아낸 부품 개수를 출력하면 되는 문제이다. UnionFind를 사용해 각 부품의 집합을 합쳐주고, 집합을 합칠 때 집합의 크기도 따로 저장해 합쳐주면 된다. Code #include #define ll long long using namespace std; ll N, arr[1000005], cnt[1000005]; ll Fin..

문제 : 13140 Hello World! 13140번: Hello World! N이 주어질 때 hello + world = N을 만족하는 서로 다른 한 자리 자연수(0 포함) d, e, h, l, o, r, w를 구해서 아래 그림과 같은 형태로 출력하는 프로그램을 작성하여라. 단, h와 w는 0이 될 수 없다. www.acmicpc.net 숫자 N이 주어질 때, hello + world = N을 만족하는 서로 다른 한자리 자연수 d, e, h, l, o, r, w를 출력하는 문제이다. next_permutation을 사용해 모든 경우의 수를 체크해 만족하는 수를 찾아 출력하면 된다. Code #include #define ll long long using namespace std; ll N; vecto..

문제 : 1162 도로포장 1162번: 도로포장 첫 줄에는 도시의 수 N(1 ≤ N ≤ 10,000)과 도로의 수 M(1 ≤ M ≤ 50,000)과 포장할 도로의 수 K(1 ≤ K ≤ 20)가 공백으로 구분되어 주어진다. M개의 줄에 대해 도로를 연결짓는 두 도시와 도로를 통과하� www.acmicpc.net 길을 지나는데 걸리는 시간과 포장해서 지나는 시간을 0으로 만들 수 있는 횟수가 주어졌을 때, 최소 시간을 구하는 문제이다. visit배열을 만들 때 1차원이 아니라 2차원으로 만든 후 Dijkstra 알고리즘을 사용해 지금까지 포장한 도로 개수당 최솟값을 구하면 된다. 최소 시간이 최대 10,000,000,000까지 커질 수 있으므로 배열의 초기값을 그보다 더 크게 잡아야 하는 것에 주의하자 Co..

문제 : 1446 지름길 1446번: 지름길 첫째 줄에 지름길의 개수 N과 고속도로의 길이 D가 주어진다. N은 12 이하이고, D는 10,000보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 지름길의 시작 위치, 도착 위치, 지름길의 길이가 주 www.acmicpc.net 고속도로의 길이와 자름길 정보가 주어질때, 운전해야하는 거리의 최솟값을 구하는 문제이다. Dijkstra 알고리즘을 사용해 최단거리를 구하면 된다. Code #include #define ll long long #define INF 1e9+7 using namespace std; struct ABC{ ll idx, dst; ABC() {} ABC(ll idx, ll dst) : idx(idx), dst(dst) {} }; bo..