블로그 언저리인 무언가

문제 : 1916 최소비용 구하기 1916번: 최소비용 구하기 첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 www.acmicpc.net 도시의 개수와 도시들 간에 운행하는 버스의 비용이 주어졌을 때 최소비용으로 이동하는 금액을 출력하는 문제이다. 다익스트라 알고리즘을 이용해서 해결하면 최소비용을 쉽게 구할 수 있다. Code #include #define ll long long #define INF 1e9+7 using namespace std; struct ABC{ ll idx, dst; ABC() {} ABC(ll idx, ..

문제 : 9375 패션왕 신혜빈 9375번: 패션왕 신해빈 첫 번째 테스트 케이스는 headgear에 해당하는 의상이 hat, turban이며 eyewear에 해당하는 의상이 sunglasses이므로 (hat), (turban), (sunglasses), (hat,sunglasses), (turban,sunglasses)로 총 5가지 이다. www.acmicpc.net 의상의 수와 이름이 주어졌을 때 맨몸이 아니도록 옷들의 조합의 수를 찾아서 출력하는 문제이다. 같은 의상의 종류를 센 후 +1씩 해서 곱해 전체 조합의 수를 세고 하나도 입지 않는 것은 불가능하므로 1을 빼서 출력하면 된다. Code #include #define ll long long using namespace std; ll N; ma..

문제 : 1080 행렬 1080번: 행렬 첫째 줄에 행렬의 크기 N M이 주어진다. N과 M은 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 행렬 A가 주어지고, 그 다음줄부터 N개의 줄에는 행렬 B가 주어진다. www.acmicpc.net 행렬 A와 행렬 B가 주어질 때 3*3 크기의 모든 원소를 뒤집어서 행렬 A를 행렬 B로 만드는 최소 횟수를 구하는 문제이다. 그리디 하게 앞 원소부터 모두 뒤집어 본 후 불가능한 경우를 체크해주면 된다. Code #include #define ll long long using namespace std; ll N, M, ans; string x[55], y[55]; int main(){ ios::sync_with_stdio(0); cin.tie(0); ..

문제 : 1074 Z 1074번: Z 한수는 2차원 배열 (항상 2^N * 2^N 크기이다)을 Z모양으로 탐색하려고 한다. 예를 들어, 2*2배열을 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하면 Z모양이다. 만약, 2차원 www.acmicpc.net 2차원 배열을 Z자 모양으로 순회 헸을 때 주어진 좌표를 몇 번째로 방문하는지 출력하는 문제이다. x, y좌표의 기준과 현재 나눌 정사각형의 한 변의 길이를 정보로 주고 분할 정복을 이용해 해결하면 된다. Code #include #define ll long long using namespace std; ll N, r, c; ll f(ll x, ll y, ll len){ if (len==0) return 0; if (r=y) ret..

문제 : 1138 한 줄로 서기 1138번: 한 줄로 서기 첫째 줄에 사람의 수 N이 주어진다. N은 10보다 작거나 같은 자연수이다. 둘째 줄에는 키가 1인 사람부터 차례대로 자기보다 키가 큰 사람이 왼쪽에 몇 명이 있었는지 주어진다. i번째 수는 0보다 www.acmicpc.net 사람의 수와 그 사람의 왼쪽에 있는 키가 큰사람의 수가 주어졌을 때 줄을 어떻게 세워야 하는지 출력하는 문제이다. 자신보다 키가 큰 사람이 왼쪽에 그 숫자만큼 위치하기 위해서는 최소한 그만큼의 빈 공간이 있어야 하는 것을 전제로 그리디 하게 접근하면 쉽게 풀 수 있다. Code #include #define ll long long using namespace std; ll N, arr[10]; int main(){ ios:..

문제 : 18115 카드 놓기 18115번: 카드 놓기 수현이는 카드 기술을 연습하고 있다. 수현이의 손에 들린 카드를 하나씩 내려놓아 바닥에 쌓으려고 한다. 수현이가 쓸 수 있는 기술은 다음 3가지다. 제일 위의 카드 1장을 바닥에 내려놓는다. www.acmicpc.net 카드를 내려놓은 순서가 주어질 때, 원래의 카드 순서를 복구하는 문제이다. deque 자료형을 이용해 앞뒤로 집어넣은 후 출력하면 된다. Code #include #define ll long long using namespace std; ll N; vector arr; deque dq; int main(){ ios::sync_with_stdio(0); cin.tie(0); cin >> N; for (int i=0;i> a; arr.p..

문제 : 2529 부등호 2529번: 부등호 여러분은 제시된 부등호 관계를 만족하는 k+1 자리의 최대, 최소 정수를 첫째 줄과 둘째 줄에 각각 출력해야 한다. 단 아래 예(1)과 같이 첫 자리가 0인 경우도 정수에 포함되어야 한다. 모든 입력 www.acmicpc.net 부등호 기호가 나열되어있는 배열이 주어질 때, 서로 다른 한 자릿수 숫자를 넣어 만족하는 가장 큰 수와 가장 작은 수를 찾아 출력하는 문제이다. 백트래킹 기법을 활용해서 모든 경우의 수를 확인해서 비교하면 된다. Code #include #define ll long long #define INF 1e15+7 using namespace std; ll N, visited[10], mn=INF, mx=-1; vector arr; void ..