🍞 Algorithm/Baekjoon

https://www.acmicpc.net/problem/1937 1937번: 욕심쟁이 판다n × n의 크기의 대나무 숲이 있다. 욕심쟁이 판다는 어떤 지역에서 대나무를 먹기 시작한다. 그리고 그 곳의 대나무를 다 먹어 치우면 상, 하, 좌, 우 중 한 곳으로 이동을 한다. 그리고 또 그곳에www.acmicpc.net풀이과정처음에는 단순하게 DFS 재귀 백트래킹을 이용하여 구현했다.하지만, DP를 사용하지 않으면 시간초과가 났다. 괜히 골드3 문제가 아니다.DP와 DFS를 같이 사용해야 하는 새로운 문제 유형이었다.만약 이 그림 (0, 0)에 판다를 냅둔다면, (0, 0) -> (0, 1) -> (0, 2) -> (1, 2) -> (1, 1) 을 통해서 총 5일을 살게 될 것이다. 그럼 dp[0][0] ..

https://www.acmicpc.net/problem/1507 1507번: 궁금한 민호 첫째 줄에 도시의 개수 N(1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에 각각의 도시 사이에 이동하는데 필요한 시간이 주어진다. A에서 B로 가는 시간과 B에서 A로 가는 시간은 같다. 또, A와 B www.acmicpc.net 풀이과정 예제 입력으로 플로이드 와샬 알고리즘을 수행한 시간이 입력된다. 그럼에도 불구하고, 플로이드 와샬을 할 때 어느 도시를 거치는 게 더 짧다면 최소 이동시간이 아니므로 이는 불가능한 경우에 해당되며 -1을 출력한다. i에서 j로 가는 경로가 k로 거쳐가는 경우와 같다면 모든 경로를 최소의 도로로 커버해야 하므로 k를 거쳐가는 도로를 선택한다. #include #inclu..

https://www.acmicpc.net/problem/21940 21940번: 가운데에서 만나기 위 조건을 만족하는 도시 $X$의 번호를 출력한다. 만약 가능한 도시 $X$가 여러 개인 경우는 도시의 번호를 오름차순으로 출력한다. www.acmicpc.net 풀이과정 #include #include #include using namespace std; int N, M, a, b, t, K, city[201]; int num[201][201]; const int INF = 1e9; void floyd() { for (int k = 1; k N >> M; for (int i = 1; i a >> b >> t; num[a][b] = t; } cin >> K; for (int i = 1; i > city[i..

https://www.acmicpc.net/problem/14938 14938번: 서강그라운드 예은이는 요즘 가장 인기가 있는 게임 서강그라운드를 즐기고 있다. 서강그라운드는 여러 지역중 하나의 지역에 낙하산을 타고 낙하하여, 그 지역에 떨어져 있는 아이템들을 이용해 서바이벌을 www.acmicpc.net 풀이과정 자신에서 자신으로 갈 수 없으니, i == j 일 때를 제외한 나머지 부분들은 무한대로 초기 설정한다. 그리고 num 배열에 각 정점에서 얻을 수 있는 아이템이 몇 개인지 입력받는다. 플로이드 와샬을 시행했을 때, 결과는 아래 사진처럼 나오게 되는데, 여기서의 숫자들은 각 노드에서 다른 노드를 갈 때 길의 길이가 얼마인지 알려주는 숫자들이다. 수색범위가 m이니까 각 노드에서 갈 때를 비교하여 ..

https://www.acmicpc.net/problem/2458 2458번: 키 순서 1번부터 N번까지 번호가 붙여져 있는 학생들에 대하여 두 학생끼리 키를 비교한 결과의 일부가 주어져 있다. 단, N명의 학생들의 키는 모두 다르다고 가정한다. 예를 들어, 6명의 학생들에 대하여 www.acmicpc.net 풀이과정 일단 각 간선의 가중치를 1로 잡았다. 자신의 키가 몇 번째인지 알 수 있으려면, 자신을 제외한 무한대가 아닌 노드들이 N - 1개여야 한다. num[i][j] = 1이라는 것은 i보다 j가 크다는 뜻이고, num[j][i] = 1이라는 것은 i보다 j가 작다는 뜻이다. 이 두 가지 경우 다 i학생의 기준에서 키의 기준을 알 수 있다. 그러므로 num[i][j] != INF 또는 num[j..

https://www.acmicpc.net/problem/2910 2910번: 빈도 정렬 첫째 줄에 메시지의 길이 N과 C가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ C ≤ 1,000,000,000) 둘째 줄에 메시지 수열이 주어진다. www.acmicpc.net 풀이 과정 #include #include #include #include #include using namespace std; map m; map m1; vector v; bool cmp(pair a, pair b) { if (a.first == b.first) return m1[a.second] b.first; } int main() { ios::sync_with_stdio(f..

https://www.acmicpc.net/problem/17219 17219번: 비밀번호 찾기 첫째 줄에 저장된 사이트 주소의 수 N(1 ≤ N ≤ 100,000)과 비밀번호를 찾으려는 사이트 주소의 수 M(1 ≤ M ≤ 100,000)이 주어진다. 두번째 줄부터 N개의 줄에 걸쳐 각 줄에 사이트 주소와 비밀번 www.acmicpc.net 풀이과정 map의 find 함수를 알게 해 준 문제이다. res를 입력받고 res의 key값을 찾으면 그에 맞는 value를 출력해주면 된다. #include #include #include #include #include using namespace std; int N, M; string adress, passwd, res; int main() { ios::sync..

https://www.acmicpc.net/problem/5568 5568번: 카드 놓기 예제 1의 경우 상근이는 11, 12, 21, 112, 121, 122, 212를 만들 수 있다. www.acmicpc.net 풀이과정 처음으로 set을 사용해봤다. map을 사용하지 않고, set을 사용한 이유는 중복되는 값을 삭제해야 되기 때문이다. 이것이 set의 가장 큰 메리트라고 생각한다. 좋은 문제인 것 같다! next_permutation - 현재 나와있는 수열에서 인자로 넘어간 범위에 해당하는 다음 순열을 구한다. - 사전식으로 정렬한다. - 사용 전에 꼭 sort하고 시작해야 한다. #include #include #include #include #include using namespace std; ..

https://www.acmicpc.net/problem/14425 14425번: 문자열 집합 첫째 줄에 문자열의 개수 N과 M (1 ≤ N ≤ 10,000, 1 ≤ M ≤ 10,000)이 주어진다. 다음 N개의 줄에는 집합 S에 포함되어 있는 문자열들이 주어진다. 다음 M개의 줄에는 검사해야 하는 문자열들이 주어 www.acmicpc.net 풀이과정 처음에는 단순히 배열에 값을 넣어서 있으면 cnt하는 반복문을 돌렸었다. 그러나 실버3은 역시 간단할리 없었다. map에 string 값을 key로 넣고 bool 값을 value로 넣어서 bool이 true라면 값이 있었다는 뜻이므로 cnt를 해줬다. #include #include #include #include using namespace std; in..

https://www.acmicpc.net/problem/1620 1620번: 나는야 포켓몬 마스터 이다솜 첫째 줄에는 도감에 수록되어 있는 포켓몬의 개수 N이랑 내가 맞춰야 하는 문제의 개수 M이 주어져. N과 M은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수인데, 자연수가 뭔지는 알지? 모르면 www.acmicpc.net 풀이과정 처음 풀어본 map 문제라 조금 헤맸던 문제이다. mp1은 string-key 값을 넣으면 int-value값이 나오는 맵이며, mp2는 int index 값을 넣으면 string이 나오는 기본적인 배열이다. #include #include #include #include using namespace std; int N, M; string str, quest;..