차가운오미자님의 유리병

https://www.acmicpc.net/problem/2164 2164번: 카드2 N장의 카드가 있다. 각각의 카드는 차례로 1부터 N까지의 번호가 붙어 있으며, 1번 카드가 제일 위에, N번 카드가 제일 아래인 상태로 순서대로 카드가 놓여 있다. 이제 다음과 같은 동작을 카드가 www.acmicpc.net 너무 쉬워서 할 말이 없다. 그냥 큐를 사용하면 된다! #include #include using namespace std; int main(void){ queue q; int n; cin >> n; for(int i=1; i1){ q.pop(); q.push(q.front()); q.pop(); } cout

https://www.acmicpc.net/problem/18258 18258번: 큐 2 첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 2,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 www.acmicpc.net 자꾸 시간초과가 나서 고생했다. 검색해보니 시간 초과가 꽤 나는 문제인 것 같다. 시간 초과가 나는 원인은: 1. 모든 기능을 별도의 함수로 정의하고 함수 콜을 하다보니 시간이 오버된다. 고로 main함수 안에 모든 코드를 때려넣어야 한다. 2. 입출력이 느리다. * 찾아보니, endl 는 스트림을 개행문자 처리 후에 flush까지 해버리기 때문에 더 costly 하다고 ..

아주 간단한 문제이다. 그냥 돈 뽑는 시간 제일 짧은 것부터 정렬해서, 각 사람마다 인출 완료까지 걸리는 시간을 출력하면 된다. #include #include #include #include using namespace std; int main(void){ vector people; int n; cin >> n; cin.ignore(); string str; getline(cin, str); stringstream ss(str); int temp; while(ss>>temp){ people.push_back(temp); } sort(people.begin(), people.end()); int result = 0; for(int i =0; i

역대급 난이도.. brute force 문제이다. 핵심은 먼저 끝나는 일부터 실행하는 것이다. 먼저 끝나는 일부터 실행할 수 있도록, 회의 시간이 담긴 벡터를 sort해주었다. sort할 때 compare함수를 정의해서 pair 형인 회의들을 정렬할 수 있게 했다. 특히 bool compare(pair a, pair b){ if(a.second < b.second){ return true; }if(a.second == b.second){ if(a.first < b.first){ return true; }else{ return false; } }else{ return false; } } 여기서 중간에 a.second == b.second 이 부분에서 다시 분기해주지 않으면 오류가 난다. 만약 끝나는 시간이..

https://www.acmicpc.net/problem/11047 11047번: 동전 0 첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000) 둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수) www.acmicpc.net Greedy 방식으로 푸는 전형적인 방식인데, 예시 입출력에서 보이지 않는 예외적인 상황들을 고려하기가 관건이다. (A) k가 동전 최대값보다 큰지, 작은지 (B) 동전이 1개(1짜리)만 주어질 경우 기본적인 아이디어는 k보다 작은 동전들중 가장 큰 동전을 빼고, k-그 동전을 해서 k가 0이 될 때까지 돌리면 되는 거라고 생각했는데..

https://www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net BFS를 구현하는 건 어렵지 않은데, 출력이 저장될 때부터 모든 토마토가 익어있는 상태이면 0을 출력해야 하고 (A), 토마토가 모두 익지는 못하는 상황이면 -1을 출력해야 하고 (B), 둘 다 아니면 모든 토마토가 다 익을 때까지 걸린 시간을 출력한다. (C) 이 부분을 처리하는 게 좀 복잡했다. A. 모든 토마토가 익어있는가? 아예 입력값을 받을 때, 0이 아닌 노드의 개수를 ..

https://www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net 1. 구상 BFS를 사용하면 된다. BFS의 특징이 최단 경로를 찾아준다는 것이다. n, m을 통해 미로의 크기를 받고, graph[][]에 미로의 길을 추상화해준다. visited[][]를 통해, 기존에 방문한 노드인지 확인해주고 check[][]에 각 노드까지의 최단 경로를 저장해준다. q는 bfs()의 지역변수로 사용해도 충분하다. isInBound()를 먼저 확인해줘서, 이동 시에 범위를 벗어나지 않도록 확인해준다. *i..

https://www.acmicpc.net/problem/1012 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 www.acmicpc.net 배추밭을 밭의 세로 가로 길이를 저장할 변수는 전역변수로 해서 각 함수에서 자유롭게 접근할 수 있도록 했다. main() 에서는 입력을 받고, for문을 통해 배추밭별로 worms()라는 필요한 배추벌레의 수를 계산하는 함수를 호출하도록 했다. - worms()와 dfs()를 호출할 때 parameter을 줄이기 위해 worms() 는 dfs()를 호출해서, 배추밭에 몇 개의 덩이(배추벌레 1마리가 처리할 수..

https://www.acmicpc.net/problem/2667 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net DFS로 풀 수 있다. 전체 그래프를 traverse하면서 1인 것 찾아서, 연결된 노드들을 0으로 바꿔주면서(dfs이용) count한다. = 단지 1개. 이게 하나의 단지니까 num_blocks에 1을 증가시킨다. 이 dfs를 하면서 단지 내에 건물 수를 센 게 count인데, 이걸 vector에 넣어서 나중에 한번에 출력할 수 있도록 한다. 그리고 다음으로 다른 단지를 생성할 1인 것을 찾고, ..

https://www.acmicpc.net/problem/2606 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어 www.acmicpc.net 간단한 traverse 문제이다. bfs를 쓰던, dfs를 쓰던 상관이 없을 것 같지만 dfs가 상대적으로 코드가 짧고 간편하니까 dfs를 사용해보았다. //num 2606 #include #include using namespace std; vector graph[101]; int visited[101]; int count = 0; void dfs(int x){ if(visited[x]==true){..