블로그 언저리인 무언가

문제 : 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:..

어제인가 그제인가 백준 1000솔브를 찍었다. 뭔가 1000솔브 기념으로 좀 어려운 문제를 풀어서 장식할까 했는데 귀찮아서 그냥 실버따리 문제로 찍게 되었다. 처음 PS 시작할 때는 1000문제 정도 풀면 잘하는 사람이 되어있을 줄 알았는데 쉬운 구현 문제 날먹으로 어느새 1000문제를 넘기게 되었다. 정작 내가 1000솔브를 찍어보니 문제수는 크게 의미가 없고 다양한 알고리즘을 알고 어려운 문제룰 푸는 게 더 중요한 거 같다. 내가 문제 푼 비율을 확인해보면 브론즈가 50%가 넘는데 진짜 이문제들은 내 실력에 하등 도움이 안 되는 문제들인 거 같다. 자주 쓰는 알고리즘들이 아니면 맨날 까먹어서 내 옛날 코드들을 찾아보게 되는데 뭔가 글을 정리해서 내가 참조할 수 있도록 블로그에 글을 쓸까 생각 중이다...

문제 : 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 ..

문제 : 2758 로또 2758번: 로또 선영이는 매주 엄청난 돈을 로또에 투자한다. 선영이가 하는 로또는 1부터 m까지 숫자 중에 n개의 수를 고르는 로또이다. 이렇게 열심히 로또를 하는데, 아직까지 한 번도 당첨되지 않은 이유는 www.acmicpc.net M이하의 수중에서 N개의 수를 뽑을 때, 앞의 수보다 2배가 되는 규칙을 따를 때 경우의 수를 세는 문제이다. 앞의 수 중에서 현재수/2보다 작은 수들의 경우의 수를 모두 더하는 DP테이블을 만들어 채운 후 모두 더해 출력하면 된다. Code #include #define ll long long using namespace std; ll T, N, M, arr[15][2005]; int main(){ ios::sync_with_stdio(0); c..