본문 바로가기

2017/03

BOJ)12100 2048 (Easy) 문제:icpc.me/12100 2048 게임에서 가능한 5번의 움직임 이내에 나올 수 있는 가장 큰 블럭을 출력하는 문제이다. 하나의 상태에서 가능한 움직임은 4방향이고 N*N의 모든 블럭이 움직여야 하므로 하나의 상태에서 4방향으로 움직일 때 연산 횟수는 4*N*N이다. 5번 움직일 때 나올 수 있는 모든 횟수는 4^5이므로 모든 경우를 전부 구했을 때 시간 복잡도는 (1024*N^2*4)이므로 완전 탐색으로 해결 가능하다. 이 때 주의해야 할 점은 한번의 움직임에서 이미 합쳐진 블럭은 다시 안합쳐지므로 visited배열을 관리해주면 된다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950.. 더보기
BOJ)13460 구슬탈출2 문제: icpc.me/13460 빨간 공과 파란 공이 동시에 움직일 때 빨간공을 구멍에 넣게하는 최소 횟수를 출력하는 문제이다. 우리는 빨간공과 파란공의 위치를 동시에 조작하며 BFS를 돌리며 횟수를 출력한다. 이 때 공이 겹치는 경우를 잘 처리해주어야 한다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374#include #include #include using namespace std;int n, m, disc[11][11][11][11], bx, by, rx, ry;char a[11][11];int .. 더보기
BOJ)1520 내리막 길 문제:icpc.me/1520 지도에서 자기보다 숫자가 낮은 곳으로 이동할 수 있을 때 0,0에서 n-1 ,m-1로 갈 수 있는 경로의 개수를 출력하는 문제이다. 우리는 다이나믹 프로그래밍을 이용하여 문제를 해결할 수 있다. dp[x][y]는 0,0에서 x,y로 이동할 수 있는 경로의 수라고 정의한 뒤 4방향 탐색으로 테이블을 채워나가면 된다. 123456789101112131415161718192021222324252627282930313233343536#include #include #include using namespace std;int dx[] = { 0,0,-1,1 };int dy[] = { -1,1,0,0 };int n, m;int chk(int x, int y) { return 0 더보기
BOJ)10422 괄호 문제: icpc.me/10422 괄호 문자열이 되려면 괄호 문자열이 채워져 나가는 과정에서 )의 개수가 (개수보다 많으면 안된다. 이를 만족하면서 채워져 나가는 길이가 N인 괄호문자열의 개수를 다이나믹 프로그래밍을 이용하여 구해주면 된다. N이 홀수인 경우 0을 출력하고 N이 짝수인 경우 dp[n/2][n/2]를 출력하면 된다. dp[x][y]의 정의는 (가 x개 )가 y개 까지 그려진 괄호문자열의 개수 이다. 점화식은 dp[x][y]=dp[x-1][y]+dp[x][y-1]이 된다. 123456789101112131415161718192021222324252627282930#include #include #include #define MOD 1000000007typedef long long ll;usin.. 더보기
BOJ)1194 달이 차오른다, 가자. 문제: icpc.me/1194 가중치 없는 그래프에서의 최단거리를 구해야 하므로 BFS를 이용하면 된다, 이때 열쇠라는 조건이 추가로 붙는데 우리는 열쇠를 쥐고 있는 상태를 비트마스킹을 통하여 표현해주면 된다. qu의 3번째 인자는 해당 상태가 가지는 열쇠를 비트로 표현한 것이다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667#include #include #include #include using namespace std;int n, m, disc[51][51][1 더보기
BOJ)2146 다리만들기 문제: icpc.me/2146 dfs를 이용하여 각 나라들을 구분해준 후 bfs를 이용하여 각 나라들에서 어떤 다른 나라로 갈 수 있는 최단 거리를 모두 구해준 뒤 그 중 최솟값을 출력해주면 된다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172#include #include #include #include #include using namespace std;int n, a[101][101], disc[101][101], c;bool chk(int x, int y) { return 0 더보기
BOJ)5427 불 문제: icpc.me/5427 가중치가 없는 그래프에서의 최단경로 이므로 BFS를 이용하여 문제를 해결해준다. 단 불이라는 새로운 조건이 존재하는데 우리는 queue에 상근이와 불을 동시에 삽입해주어 불일 경우와 상근이일 경우를 다르게 처리해주면 된다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384#include #include #include #include using namespace std;int t, w, h, sx, sy;char a[1001][1001];in.. 더보기
BOJ)1745 숨기 문제: icpc.me/1745 F개의 방이 있을 때 각방마다 학생들이 숨을 수 있는 수와 현재 몇명의 학생들이 있는지 수가 주어진다. 이 때 방 A에서 B로 이동할 때 걸리는 시간이 주어질 때 모든 학생이 숨을 수 있는 최소 시간을 구하는 문제이다. 우리는 소스 -> I번 방 -> I번 방에서 ->J번 방으로 연결 된 정점 -> J번 방 ->싱크로 모델링을 하여 모든 학생들이 숨을 수 있는지 여부를 알 수 있다. 이때 capacity를 소스 -> I번 방은 현재 i번방에 있는 학생 수 / J번 방 -> 싱크는 j번 방에 숨을 수 있는 학생 수 나머지는 INF를 주면 된다. 이렇게 하여서 흘린 maximum flow가 현재 있는 학생들의 수의 총합과 같다면 현재 모델링에서 학생들이 전부 숨을 수 있는것이다.. 더보기
BOJ)5397 키로거 문제:icpc.me/5397 메모장에 커서의 입력하는 단어와 커서의 움직임과 누른 백스페이스가 기록될 때 최종적으로 남는 단어를 출력하는 문제이다. 중간에 삽입 삭제가 가능한 링크드리스트를 구현하여 해결할 수 있다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091#include #include using namespace std;struct Node { char data; Node *prev, *next; Node() :data('\0'), pr.. 더보기
BOJ)2075 N번째 큰 수 문제:icpc.me/2075 N^2개의 수가 들어올 때 N번째로 큰 수를 구하는 문제이다. N이 최대 1500 밖에 안들어오므로 단순히 값을 다 받아서 정렬해주는 N^2logN의 해법으로 해결할 수 있다. 하지만 메모리제한이 10MB이므로 힙을 이용하여 수를 받을 때 마다 큰 수 N개만큼만 저장해주고 그 수들중 가장 작은 수와 들어오는 수를 비교를하여 힙을 관리해주면 된다. 123456789101112131415161718192021222324#include #include #include using namespace std;int n, x;priority_queue pq;int main() { scanf("%d", &n); for (int i = 0; i 더보기

티스토리툴바