-
1. 문제
2. 코드
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475#include "pch.h"#include <stdio.h>#include <queue>#define _CRT_SECURE_NO_WARNINGSusing namespace std;struct water{int a, b, c;};int A, B, C;bool visit[202][202], ans[202];int main(){scanf("%d %d %d", &A, &B, &C);queue<water> q;q.push({ 0,0,C });while (!q.empty()){water cur = q.front();q.pop();if (visit[cur.a][cur.b])continue;visit[cur.a][cur.b] = true;if (cur.a == 0)ans[cur.c] = true;//a->bif (cur.a + cur.b > B)q.push({ cur.a + cur.b - B,B,cur.c });elseq.push({ 0,cur.a + cur.b,cur.c });//a->cif (cur.a + cur.c > C )q.push({ cur.a + cur.c - C,cur.b,C });elseq.push({ 0, cur.b, cur.a + cur.c });//b->aif (cur.b + cur.a > A )q.push({ A,cur.b + cur.a - A,cur.c });elseq.push({ cur.b + cur.a,0,cur.c });//b->cif (cur.b + cur.c > C )q.push({ cur.a,cur.b + cur.c - C,C });elseq.push({ cur.a,0,cur.c + cur.b });//c->aif (cur.c + cur.a > A)q.push({ A,cur.b,cur.c + cur.a - A });elseq.push({ cur.c + cur.a,cur.b,0 });//c->bif (cur.c + cur.b > B)q.push({ cur.a,B,cur.c + cur.b - B });elseq.push({ cur.a,cur.b + cur.c,0 });}for (int i = 0; i < 202; i++) {if (ans[i])printf("%d ", i);}}cs 3. 후기
내가 이문제를 풀었을 때는 메모리가 이 코드의 몇십배였다. 방문검사를 일단 넣고나서 하며, q.push()에 한 줄로 원하는 값을 넣을 수 있어서 값을 저장할 필요가 없다. 나는 값을 저장할 임시 배열을 만들어서 하고 방문검사를 할 때 굳이 a,b,c다 검사를 했다. 생각해보면 셋 중에 두개만 검사를 해도 상관이 없다.
'알고리즘 > 백준' 카테고리의 다른 글
9376 탈옥 (0) 2019.03.14 12851 숨바꼭질 2 -BFS (0) 2019.03.12 1525 퍼즐 (0) 2019.03.12 9019 DSLR (0) 2019.03.11 7453 합이 0인 네 정수 (0) 2019.03.10