그리디10 [백준 1080] 행렬 www.acmicpc.net/problem/1080 1080번: 행렬 첫째 줄에 행렬의 크기 N M이 주어진다. N과 M은 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 행렬 A가 주어지고, 그 다음줄부터 N개의 줄에는 행렬 B가 주어진다. www.acmicpc.net 그리디 알고리즘이라는데 그리디는 알다가도 모르겠다.. 연산 방식은 1. 두 개의 행렬이 같으면 1 다르면 0으로 표시 2. 1의 행렬에 대해 3*3 뒤집기 연산을 수행 2-1. 연산을 수행할 때 마다 모든 행렬 값이 0이 되는지 확인 2-2. 모든 행렬이 0이라면 연산 횟수 리턴 2-3. 그렇지 않다면 다음 연산 수행 먼저 두 행렬을 비교하여 check배열을 만들고 다른 원소 수를 센다. for (int i = 0; i < .. 2021. 1. 24. [백준 13305] 주유소 www.acmicpc.net/problem/13305 13305번: 주유소 표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에는 도시의 개수를 나타내는 정수 N(2 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 인접한 두 도시를 연결하는 도로의 길이가 제일 왼쪽 도로부터 N-1 www.acmicpc.net 그리디를 사용하는 문제이다. 처음엔 뒤에서 부터 접근했는데 그렇게 해선 못푼다 ㅠ 왜냐면 처음부터 현재 시점 사이에서 가장 작은 값이 전체 값에 영항을 주기 때문. 따라서 앞에서 부터 비용을 확인하면서 만약 현재 값이 minCost이거나 minCost보다 크다면 -> 거리를 누적시킨다. 현재 값이 minCost보다 작다면 -> (어차피 지금 등장한 작은값은 앞에 누적거리에 영향을 못미침) 이전 누.. 2021. 1. 14. [백준 2262] 토너먼트 만들기 www.acmicpc.net/problem/2262 2262번: 토너먼트 만들기 월드시에서는 매년 n명의 사람들이 모여 월드 크래프트라는 게임의 토너먼트 대회를 치른다. 이 게임은 특성상 실력만이 승패를 좌우하기 때문에, 아무리 실력이 엇비슷한 사람이 시합을 치러 www.acmicpc.net 그리디 알고리즘 첨에 우선순위큐를 쓰려했는데 위치가 고정이라 힘들것 같아서 단순 배열을 사용했다. 로직은 이렇다. 가장 큰 등수인 n부터 양쪽을 살펴서 차이가 작은 쪽을 택해서 그 차를 정답에 더하는 것이다. 그리고 나서 가장 큰 등수는 팝해준다. #include #include using namespace std; int n; int arr[256]; int main(void) { scanf("%d", &n); f.. 2020. 12. 31. [백준 20310] 타노스 www.acmicpc.net/problem/20310 20310번: 타노스 어느 날, 타노스는 0과 1로 이루어진 문자열 $S$를 보았다. 신기하게도, $S$가 포함하는 0의 개수와 $S$가 포함하는 1의 개수는 모두 짝수라고 한다. 갑자기 심술이 난 타노스는 $S$를 구성하는 문자 www.acmicpc.net 문자열 알고리즘 문제 문자열 내의 순서는 고정이라는 전제하에 풀어야 한다. 아니면 25점 ㅠ 0과 1 절반씩을 날린다고 했으므로 사전순으로 빠른 것을 구하기위해 0은 뒤에 절반을, 1은 앞에 절반을 날린다.ㅏ 덱을 사용해도 되지만 배열에서 해결하기 위해 머지소트에서 사용하는 로직을 사용했다. #include #include #include using namespace std; char s[501].. 2020. 12. 31. 이전 1 2 3 다음