차가운오미자님의 유리병

https://www.acmicpc.net/problem/2775 2775번: 부녀회장이 될테야 첫 번째 줄에 Test case의 수 T가 주어진다. 그리고 각각의 케이스마다 입력으로 첫 번째 줄에 정수 k, 두 번째 줄에 정수 n이 주어진다 www.acmicpc.net 문제 이해 아래 층부터 채워나가면 된다. 각 칸의 패턴을 파악하면 금방 식을 세워서 해결할 수 있다. 1호 2호 3호 1층 0+1 = 1 1+2 = 3 1+2+3 = (1+2) + 3 = 6 0층 1 2 3 보면 각 k층 n호는 k-1층의 1부터 n호까지의 합인데, k-1층의 1부터 n-1호까지의 값이 k층 n-1호에 있으므로, k-1층 n호 + k층 n-1호의 값을 더하면 된다. 주어지는 테스트 케이스가 여러 개여서, 그냥 14층 14..

https://www.acmicpc.net/problem/2292 2292번: 벌집 위의 그림과 같이 육각형으로 이루어진 벌집이 있다. 그림에서 보는 바와 같이 중앙의 방 1부터 시작해서 이웃하는 방에 돌아가면서 1씩 증가하는 번호를 주소로 매길 수 있다. 숫자 N이 주어졌 www.acmicpc.net 문제 이해 수열이 1, 6, 12 로 늘어나는 것을 확인하면 된다. 1: 1번 2~7: 2번 8~19 : 3번 .... 이런식으로 늘어간다. 작성 코드 (C++) #include using namespace std; int N; int main(void){ cin >> N; if(N==1) { printf("1"); return 0; } int i; int no = 1; for(i = 1; ;i++){ n..

모든 요소를 탐색하면서 요구사항에 맞게 동작하면 된다. DFS를 이용하거나 BFS를 사용하는데 1. DFS를 사용할 경우 코드가 간단하지만, map이 크면 메모리 부족이 일어날 수 있고, 디버깅이 어렵다 2. BFS는 맵이 너무 클 경우에 사용한다. https://chagaun-omija.tistory.com/71 [백준] 2667: 단지번호붙이기 https://www.acmicpc.net/problem/2667 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번 chagaun-omija.tistory.com 여기 있는 이 문제가 Flood Fill의 예시 문제이다. 문제 해설처럼 맵에서 ..

http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=954 JUNGOL www.jungol.co.kr 문제 이해 가능한 경로들 중에 최적의 경로를 찾는 것이기 때문에 (최소 비용 구하기) DFS를 돌리면 되는 문제이다. Depth 는 총 배달해야 하는 장소의 개수 (12)이다. 사실 12개의 초이스들을 12번 선택해야 하기 때문에 상당히 수가 크지만, (12!) 이미 방문한 곳은 다시 방문하지 않기 때문에 충분히 작아질 수 있다. 또한, 마지막 가지치기를 하면 생각보다 가지가 많이 뻗지 않을 수있다. 기본적으로 DFS를 돌릴 때는 depth가 12가 넘어가지 않는 정도면 해낼 수 있다고 생각하면 된다. 회사(1)에서 출발해서, 가능한 경로들을 하나하나..

https://www.acmicpc.net/problem/1966 1966번: 프린터 큐 여러분도 알다시피 여러분의 프린터 기기는 여러분이 인쇄하고자 하는 문서를 인쇄 명령을 받은 ‘순서대로’, 즉 먼저 요청된 것을 먼저 인쇄한다. 여러 개의 문서가 쌓인다면 Queue 자료구조에 www.acmicpc.net 문제 이해 FIFO 방식이라고 했으므로 큐를 이용하는 문제이다. 문서를 앞부터 하나하나 체크하면서, 뒤에 우선순위가 자기보다 높은 애가 있으면 프린트하지 않고 다시 큐의 뒤에 넣어준다. 관건은 우선순위가 자기보다 높은 애가 있는지를 판단하는 것이다. 우선순위가 1부터 9로 범위가 작으므로 각 우선순위 별로 문서가 몇 개가 있는지를 확인하면 편하다. 이를 위해서 우선순위 별 문서 수를 저장한 배열을 이..

http://jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=934&sca=99&page=7 JUNGOL www.jungol.co.kr 문제 이해 최단 거리를 구하는 문제이므로 BFS를 사용하면 된다. 출발지로부터 모든 상하좌우를 탐색하면서 방문하다가 목적지에 도착하면 거기까지의 거리를 return해주면 된다. 여기서 주어진 map의 0인 부분만 탐색해야 한다. 시간복잡도는 맵의 모든 부분이 0이어서 모든 곳을 탐색하는 경우 (100*100) 정도 이다. 충분히 시간 내에 해결할 수 있다. 작성 코드 #include #include using namespace std; int Y, X; int sy, sx, ey, ex; char map[100 * 10][100 * ..

http://jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=386&sca=30 JUNGOL www.jungol.co.kr 문제 이해 현재 말의 위치에서 졸의 위치까지 최단 거리로 이동하는 문제이므로 BFS를 사용하면 된다. 모든 경우를 탐색하는 경우가 아니라, 졸의 위치에 도착하면 BFS를 끝내면 된다. 시간복잡도: 현재 위치에서 BFS를 수행하므로 약 100*100 (가로세로 최대길이)만큼을 반복할 것이다. 작성 코드(C) #include int N, M; // 행, 열 int R, C; // 말이 있는 행, 열 int S, K; // 졸이 있는 행, 열 int visited[100 + 10][100 + 10]; // 방향 벡터 int dy[] = { -2, -2..

https://www.acmicpc.net/problem/2589 2589번: 보물섬 첫째 줄에는 보물 지도의 세로의 크기와 가로의 크기가 빈칸을 사이에 두고 주어진다. 이어 L과 W로 표시된 보물 지도가 아래의 예와 같이 주어지며, 각 문자 사이에는 빈 칸이 없다. 보물 지도의 www.acmicpc.net 문제 이해 최단 거리를 구하는 문제이므로 BFS를 사용하면 된다. 모든 땅 중 두 개를 골라 그 사이의 최단거리를 구해야 하고, 그렇게 나온 최단거리들 중에 최장 거리를 고르는 것이 답이다. 그러므로 모든 땅들 중 두 개씩 짝지어서 모두 BFS를 해야한다. 시간 복잡도를 살펴보면, 가로 세로 최고 50개이니까, 50*49번의 BFS가 일어나고, 각 BFS별로 약 50*50번의 루프가 발생한다치면 25..

https://www.acmicpc.net/problem/15651 15651번: N과 M (3) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 문제 이해 Backtracking을 하면서 모든 경우를 탐색하면 된다. DFS를 사용한다. 작성 코드 #include using namespace std; int N, M; int ans[9]; void BackTracking(int cnt){ if(cnt == M){ for(int i = 0; i

https://www.acmicpc.net/problem/15650 15650번: N과 M (2) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 문제 이해 DFS를 이용해서 모든 수열을 구하면 된다. 작성 코드 #include using namespace std; int N, M; int visited[9]; int ans[9]; void Check(int cnt, int start){ if(cnt == M){ for(int i = 0; i