차가운오미자님의 유리병

역대급 난이도.. 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){..

10773번. 제로 https://www.acmicpc.net/problem/10773 10773번: 제로 첫 번째 줄에 정수 K가 주어진다. (1 ≤ K ≤ 100,000) 이후 K개의 줄에 정수가 1개씩 주어진다. 정수는 0에서 1,000,000 사이의 값을 가지며, 정수가 "0" 일 경우에는 가장 최근에 쓴 수를 지우고, 아닐 경 www.acmicpc.net 간단한 스택 문제이다. 그냥 스택 구조만 이해하면 바로 풀 수 있는 문제. //num 10773 #include #include using namespace std; int main(void){ int k, n; stack s; int answer = 0; cin >> k; //cin.ignore(); for(int i = 0; i> n; //..

2231번 https://www.acmicpc.net/problem/2231 2231번: 분해합 어떤 자연수 N이 있을 때, 그 자연수 N의 분해합은 N과 N을 이루는 각 자리수의 합을 의미한다. 어떤 자연수 M의 분해합이 N인 경우, M을 N의 생성자라 한다. 예를 들어, 245의 분해합은 256(=245+2+4+5)이 www.acmicpc.net brute-force 방식으로 푸는 문제이다 나는 getparts()라는 함수를 별도로 정의해서 했는데, 사실 별도로 정의할 필요없이 바로 메인 함수에 때려넣어도 충분하다. 나는 구조화할 때, 어떤 기능을 할 함수를 가정해서 메인함수를 일단 짜버리는게 생각하기 편해서 그랬다. 1. 핵심은 목표한 m이라는 숫자를 생성할 수 있는 숫자를 찾기 위해서 1부터 m까..

구글 인앱 결제 논란 7월부터 구글에서 '구글 플레이'에서 콘텐츠, 게임 아이템 등으로 거래되는 앱의 결제 수수료를 연매출 11억원까지는 15%, 그 이상부터는 30%를 부과하기로 결정. 그리고 모든 디지털 콘텐츠 앱을 대상으로 의무 시행하겠다고 함. 수수료를 인하한 배경에는 인앱 결제를 강제화함으로서 비판에 맞딱뜨렸기 때문. 애플은 결제 수수료를 15%로 인하하며 그 대상을 연 매출 100만달러 이하 기업'으로 한정했다. 여기에 논란이 되는 점은 인앱 결제를 강제화하고, 이에 대해 수수료를 받는 것이 독점의 폐해 아니냐는 것이다. 안드로이드 폰을 사용하면 구글 플레이를 이용해 앱을 결제하는 것이 일반적인데, 모든 앱 결제에 수수료를 받으니까, 독점이라는 점을 이용하는 것 아니냐고... 인앱 결제를 강제..