본문 바로가기
728x90
반응형

Algorithm

 (120)
[C++] 17610 : 양팔저울 https://www.acmicpc.net/problem/17610 17610번: 양팔저울 무게가 서로 다른 k개의 추와 빈 그릇이 있다. 모든 추의 무게는 정수이고, 그릇의 무게는 0으로 간주한다. 양팔저울을 한 번만 이용하여 원하는 무게의 물을 그릇에 담고자 한다. 주어진 모든 추 www.acmicpc.net #include using namespace std; #define MAX 2600003 int k; //추의 개수 int g; //추의 무게 int S; bool d[15][MAX]; int ans; int main(void) { cin >> k; int i, j; d[0][0] = true; for (i = 1; i > g; S += g; for (j = 0; j < MAX - g; j++)..
[C++] 1103 : 게임 https://www.acmicpc.net/problem/1103 1103번: 게임 줄에 보드의 세로 크기 N과 가로 크기 M이 주어진다. 이 값은 모두 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 보드의 상태가 주어진다. 쓰여 있는 숫자는 1부터 9까지의 자연수 또는 www.acmicpc.net #include #include using namespace std; int N, M; //row,column int MAP[55][55]; //H는 0으로 표현 int mr[] = { -1,1,0,0 }; int mc[] = { 0,0,-1,1 }; int d[55][55]; //DP table bool visit[55][55]; //방문했는지 확인 int f(int i, int j) { //M..
[C++] 2629 양팔저울 https://www.acmicpc.net/problem/2629 2629번: 양팔저울 첫째 줄에는 추의 개수가 자연수로 주어진다. 추의 개수는 30 이하이다. 둘째 줄에는 추의 무게들이 자연수로 가벼운 것부터 차례로 주어진다. 같은 무게의 추가 여러 개 있을 수도 있다. 추의 무 www.acmicpc.net #include using namespace std; int m, a[33], n, b; //m:추의 개수, a:추의 무게들, n:확인할 추의 개수, b:확인할 추의 무게들 bool d[33][15001]; void f(int depth,int weight) { //종료조건 if (depth > m) return; //중복조건 if (d[depth][weight]) return; //dp d[dep..
[C++] 2293 : 동전 1 https://www.acmicpc.net/problem/2293 2293번: 동전 1 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. www.acmicpc.net #include using namespace std; int n, k; int c; int d[10001]; int main(void) { cin >> n >> k; int i, j; d[0] = 1; for (i = 0; i > c; for (j = c; j
[C++] 1106 : 호텔 https://www.acmicpc.net/problem/1106 1106번: 호텔 첫째 줄에 C와 형택이가 홍보할 수 있는 도시의 개수 N이 주어진다. C는 1,000보다 작거나 같은 자연수이고, N은 20보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 각 도시에서 홍보할 때 www.acmicpc.net #include #include #include using namespace std; #define MAX 111111 int C, N; int a, b; //a:홍보할 때 드는 비용. b:그 비용으로 얻을 수 있는 고객의 수 vector v; ////DP table. index는 비용. D[index]는 비용당 가능한 최대 인원 int main(void) { cin >> C >> N; int..
[C++] 1149 : RGB거리 https://www.acmicpc.net/problem/1149 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net #include #include using namespace std; int N; int R, G, B; int d[1111][3]; //0은 R, 1은 G, 2는 B int ans=1e9; int main(void) { cin >> N; int i, j; for (i = 1; i > R >> G >> B; d[i][0] = min(d[i - 1][1], d[i - 1][2]..
[C++] 1987 : 알파벳 https://www.acmicpc.net/problem/1987 1987번: 알파벳 세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으 www.acmicpc.net #include #include using namespace std; int R, C; char a[23][23]; bool isPos[26]; int ans; void f(int i,int j,int depth) { if (i > 1 && isPos[a[i][j] - 'A']) {//상 isPos[a[i][j] - 'A'] = false; f(i - 1, j, depth + 1); isP..
[C++] 11660 : 구간 합 구하기 5 https://www.acmicpc.net/problem/11660 11660번: 구간 합 구하기 5 첫째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다. (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000) 둘째 줄부터 N개의 줄에는 표에 채워져 있는 수가 1행부터 차례대로 주어진다. 다음 M개의 줄에는 네 www.acmicpc.net #include using namespace std; int N, M; int a[1111][1111]; //입력받는 배열 int d[1111][1111]; //DP table 생성 int ans; //출력(정답) int main(void) { //cin, cout 빠르게 해주기(안하면 시간초과 일어남) ios_base::sync_with_stdio(fa..
728x90
반응형

티스토리툴바