hwooo

https://www.acmicpc.net/problem/3055 3055번: 탈출 사악한 암흑의 군주 이민혁은 드디어 마법 구슬을 손에 넣었고, 그 능력을 실험해보기 위해 근처의 티떱숲에 홍수를 일으키려고 한다. 이 숲에는 고슴도치가 한 마리 살고 있다. 고슴도치는 제 www.acmicpc.net 풀이 이차원 배열을 사용하여 티떱숲의 지도를 저장한다. 이 때 물인 지점은 W에 저장하고 도착지와 돌의 위치는 음수로, 빈 칸은 양수로 저장 Water 함수 : 해당 지점에 물이 차오르는 시점을 저장 - BFS입력 시에 저장했던 물의 위치를 시작으로 맵의 모든 지점을 탐색 Route 함수: 시작지점(S) 부터 해당지점에 도달하는 시점을 저장 - BFS물이 차있거나 찰 예정인 지점은 갈 수 없음탐색 중 도착지를..

https://www.acmicpc.net/problem/2156 2156번: 포도주 시식 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규 www.acmicpc.net 풀이 3잔을 연속으로 마시면 안 되므로 3번째 잔부터 조건을 고려해줌 ?OOX - DP[i-1] ?XOO - DP[i-3]+wine[i-1]+wine[i] ?OXO - DP[i-2]+wine[i] i번째 순서에 최대값이 나올 조건은 위의 3개이므로 이를 고려하여 DP로 코드를 구현 밑의 링크의 설명이 자세해서 문제 풀 때 도움을 많이 얻었다! https://yabmoons.tistory.com/51..

https://www.acmicpc.net/problem/1707 1707번: 이분 그래프 입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V와 간선의 개수 E가 빈 칸을 사이에 www.acmicpc.net 풀이 - BFS 사용, 레벨 별로 다른 값을 visited 배열에 저장하여 이분 그래프를 구분.- 같은 레벨의 노드끼리 값이 다를 수 있으므로 방문 여부와 상관 없이 모든 노드에서 탐색이 필요 (이 때, Q.push()는 방문하지 않는 노드에 한해서만 시행되므로 이미 방문한 노드 탐색 시에는 한 단계 아래 레벨만 탐색) 코드 #include #include #include #include usin..

https://www.acmicpc.net/problem/2250 2250번: 트리의 높이와 너비 첫째 줄에 노드의 개수를 나타내는 정수 N(1 ≤ N ≤ 10,000)이 주어진다. 다음 N개의 줄에는 각 줄마다 노드 번호와 해당 노드의 왼쪽 자식 노드와 오른쪽 자식 노드의 번호가 순서대로 주어진다. www.acmicpc.net 풀이 입력 받은 후 루트를 찾고, 트리를 중위순회하며 루트 값을 레벨에 따라 나눠서 저장했다. 탐색되는 순서가 노드의 가로 위치이므로 cnt로 위치를 세어주었다.마찬가지로 Height 벡터에 레벨 별로 나뉘어 저장된 노드들도 왼쪽부터 순서대로 저장되어 있으므로 (마지막에 저장된 노드)-(처음 저장된 노드)의 값이 해당 레벨에서의 최대 넓이이다. - 입력은 순서대..

https://www.acmicpc.net/problem/16236 16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가 www.acmicpc.net 풀이 BFS로는 상어가 다음으로 이동할 위치와 해당 위치까지의 거리를 찾았다. 이동 순서를 상, 좌, 우, 하로 설정해서 가장 처음 먹을 수 있는 위치가 문제의 조건을 만족하는 줄 알았지만 아니어서, 우선순위 큐를 사용하여 가장 위쪽, 왼쪽에 위치한 좌표를 찾았다. 상어의 크기, 이동 시간 및 종료 조건은 Eat함수로 계산했다. 주의했던 점 - 상어의 초기 위치의 값은 0으로, 항상 지나갈..

https://www.acmicpc.net/problem/2665 2665번: 미로만들기 첫 줄에는 한 줄에 들어가는 방의 수 n(1 ≤ n ≤ 50)이 주어지고, 다음 n개의 줄의 각 줄마다 0과 1이 이루어진 길이가 n인 수열이 주어진다. 0은 검은 방, 1은 흰 방을 나타낸다. www.acmicpc.net 풀이 이 문제는 가장 빠른 경로를 찾는 것이 아닌 바꾼 벽의 개수가 최소인 경로를 찾는 문제이므로 bfs를 약간 변형해서 풀었다. 방문 여부가 아닌 현재 지점에 도달하기까지 바꾼 벽의 개수를 저장했다.따라서 초기값은 문제에서 나올 수 없는 큰 값으로 설정해놓고, 시작지점의 값을 0으로 설정한 후에 탐색을 하며 벽이 바뀌어야 할 경우 값을 증가시키며 bfs를 실행했다.이 때, 탐색하고자 하는 지점에..

https://www.acmicpc.net/problem/1759 1759번: 암호 만들기 첫째 줄에 두 정수 L, C가 주어진다. (3 ≤ L ≤ C ≤ 15) 다음 줄에는 C개의 문자들이 공백으로 구분되어 주어진다. 주어지는 문자들은 알파벳 소문자이며, 중복되는 것은 없다. www.acmicpc.net 풀이 입력 받은 문자를 오름차순으로 정렬 후, 브루트포스 알고리즘을 이용하여 모든 경우의 수를 계산하였다. 문자를 하나 추가할 때마다 오름차순인지 확인해주었고, 문자열의 길이가 암호의 길이가 됐을 때 저장하였다. 해당 코드엔 set에 저장했지만 문자들이 이미 정렬되어 있는 상태로 탐색하므로 벡터에 저장해도 된다. 코드 #include #include #include #include #include #i..

https://www.acmicpc.net/problem/1235 1235번: 학생 번호 첫째 줄에는 학생의 수 N(2≤N≤1,000)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 학생의 학생 번호가 순서대로 주어진다. 모든 학생들의 학생 번호는 서로 다르지만 그 길이는 모두 같으며, 0부 www.acmicpc.net 풀이 학생 번호는 최대 100자리이므로 문자열 사용. 문자열에서 뒤의 k자리만 추려서 set에 저장한 다음 set의 크기와 학생의 수가 같다면 모든 학생들의 번호가 다른 것이므로 k출력. 코드 #include #include #include #include #include using namespace std; set S; vector V; void Get_K(int N, int len) ..