-
[BOJ] 4586 : Image Compression
4586 : Image Compression 풀이 흑흑 문제를 잘못 읽어서 한 번 틀렸다 ㅠㅠ 네 조각씩 나눠서 분할정복을 하면 된다. 제한이 크지 않으므로 나이브하게 사각형을 다 돌아보면 된다. 룰루 코드 #include <stdio.h> #define y1 fuck typedef double db; int n, t; char a[66][66]; void go(int x1, int y1, int x2, int y2) { if (x1 == x2 && y1 == y2) return; int siz = (x2 - x1 + 1) * (y2 - y1 + 1),...
-
[BOJ] 6191 : Cows on Skates
6191 : Cows on Skates 풀이 (1,1)~(r,c)까지의 경로를 찾아주자! 왜 이게 usaco gold 문제인지는 모르겠다 ㅋㅋㅋ 코드 #include <stdio.h> #include <algorithm> #include <queue> using namespace std; const int dx[] = { 0,0,-1,1 }, dy[] = { -1,1,0,0 }; struct ABC { int x, y; }; int n, m; char a[123][123]; ABC chk[123][123]; queue<ABC> que; void f(int x, int y) { if (x != 1 || y != 1) f(chk[x][y].x, chk[x][y].y); printf("%d %d\n", x, y); }...
-
[BOJ] 2786 : 상근이의 레스토랑
2786 : 상근이의 레스토랑 풀이 (첫 주문) 가격과 (일반 주문) 가격이 나누어져있다. 일반 가격으로 정렬한 뒤 1~i번째 가격의 합을 구해놓고 생각하자. 그럼 두 가지의 케이스로 나눌 수 있다. 1~i번째 메뉴들 중 (첫 주문)과 (일반 주문) 가격의 차이가 가장 큰 것을 고르는 경우 i~n번째 메뉴들 중 (첫 주문)의 가격이 가장 작은 것을 고르는 경우 이제 어찌저찌여차저차 잘 짜면 된다. 코드 #include <stdio.h> #include <algorithm> #define fst first #define snd second using namespace std; typedef pair<int, int>...
-
[BOJ] 2785 : 체인
2785 : 체인 풀이 데스크립션이 이상해서 한참 고민했다 (…) 고리로 이루어진 체인들이 여럿 주어진다. 고리를 최소한으로 사용해서 모든 체인들을 일렬로 연결하고 싶다. 한 고리에는 최대 두 개의 다른 고리(체인)만 연결할 수 있다. 그리디하게 생각해보자! 체인의 수가 작아지면 필요한 고리의 수도 작아진다. 그리고 체인을 모두 고리로 분해하면 체인의 개수가 하나 줄어든다.! 길이가 가장 짧은 체인의 고리부터 사용하면 된다! 같은 양의 고리를 사용하더라도 길이가 짧은 것부터 사용해야 체인의 수를 조금이나마 더 줄일 수 있다. 코드 #include <stdio.h>...
-
[BOJ] 2784 : 가로 세로 퍼즐
2784 : 가로 세로 퍼즐 풀이 n 제한이 굉장히 작으므로 naive하게 그냥 다 돌려보면 된다! 코드 #include <iostream> #include <string> #include <algorithm> using namespace std; string pzl[3], wrd[6]; void wookje() { bool chk[6] = { 0 }; int cnt = 0; for (int k = 0; k < 3; k++) { for (int i = 0; i < 6; i++) { if (!chk[i] && pzl[k] == wrd[i]) { chk[i] = 1, cnt++; break; } }...