그리디
-
Problem : https://leetcode.com/problems/score-after-flipping-matrix/ Difficulty : Medium Status : Solved Time : ??:??:?? 문제 설명 풀이 비트마스킹은 너무 느렸다...! 좀 더 간결히, 그리고 문제의 본질을 꿰뚫어야 풀 수 있는 문제였다. 언뜻 보면 모든 경우의 수를 다 테스트해보아야 할 것 같지만, 함정이 있다. score는 이진법으로 계산되므로, 제일 높은 차수(0번째 column)가 모두 1인 경우가 그리디하게 가장 큰 값을 지니게 된다. 즉 column 0을 1로 세팅하도록 하자. 이제 column 1부터 순회를 시작하면 된다. 이 때, column 0이 원래 1인 경우는 row가 뒤집어진 경우이므로..
861. Score After Flipping MatrixProblem : https://leetcode.com/problems/score-after-flipping-matrix/ Difficulty : Medium Status : Solved Time : ??:??:?? 문제 설명 풀이 비트마스킹은 너무 느렸다...! 좀 더 간결히, 그리고 문제의 본질을 꿰뚫어야 풀 수 있는 문제였다. 언뜻 보면 모든 경우의 수를 다 테스트해보아야 할 것 같지만, 함정이 있다. score는 이진법으로 계산되므로, 제일 높은 차수(0번째 column)가 모두 1인 경우가 그리디하게 가장 큰 값을 지니게 된다. 즉 column 0을 1로 세팅하도록 하자. 이제 column 1부터 순회를 시작하면 된다. 이 때, column 0이 원래 1인 경우는 row가 뒤집어진 경우이므로..
2024.05.14 -
Problem : https://leetcode.com/problems/maximize-happiness-of-selected-children Difficulty : Medium Status : Solved Time : ??:??:?? 문제 설명 풀이 릿코드에서 맞닥뜨린 한국적인(?) 문제. 지금껏 릿코드 문제를 풀어서 느꼈던 점은. 왠지 백준 골드문제를 달아줘도 손색없을 난이도였다. 그리디로 접근해보자. 어떻게 사람을 뽑던 간에, 최종적으로 k명의 사람을 뽑으므로 감소치는 최대 k*(k-1)/2명이 될 것이다. happiness value는 음수가 될 수 없다. 즉 매 순간 행복도가 최대치인 아이들을 뽑고, 어느 시점에서 행복도 최대치가 0이라면 감소는 더 이상 적용되지 않는다. 즉 내림차순으로 정..
3075. Maximize Happiness of Selected ChildrenProblem : https://leetcode.com/problems/maximize-happiness-of-selected-children Difficulty : Medium Status : Solved Time : ??:??:?? 문제 설명 풀이 릿코드에서 맞닥뜨린 한국적인(?) 문제. 지금껏 릿코드 문제를 풀어서 느꼈던 점은. 왠지 백준 골드문제를 달아줘도 손색없을 난이도였다. 그리디로 접근해보자. 어떻게 사람을 뽑던 간에, 최종적으로 k명의 사람을 뽑으므로 감소치는 최대 k*(k-1)/2명이 될 것이다. happiness value는 음수가 될 수 없다. 즉 매 순간 행복도가 최대치인 아이들을 뽑고, 어느 시점에서 행복도 최대치가 0이라면 감소는 더 이상 적용되지 않는다. 즉 내림차순으로 정..
2024.05.09 -
Problem : https://www.acmicpc.net/problem/1285 1285번: 동전 뒤집기 첫째 줄에 20이하의 자연수 N이 주어진다. 둘째 줄부터 N줄에 걸쳐 N개씩 동전들의 초기 상태가 주어진다. 각 줄에는 한 행에 놓인 N개의 동전의 상태가 왼쪽부터 차례대로 주어지는데, 앞면이 위 www.acmicpc.net Difficulty : Gold 1 Status : Solved Time : 00:39:59 문제 설명 더보기 N2개의 동전이 N행 N열을 이루어 탁자 위에 놓여 있다. 그 중 일부는 앞면(H)이 위를 향하도록 놓여 있고, 나머지는 뒷면(T)이 위를 향하도록 놓여 있다. 은 N이 3일 때의 예이다. 이들 N2개의 동전에 대하여 임의의 한 행 또는 한 열에 놓인 N개의 동전을 ..
[백준/1285] 동전 뒤집기 (Python)Problem : https://www.acmicpc.net/problem/1285 1285번: 동전 뒤집기 첫째 줄에 20이하의 자연수 N이 주어진다. 둘째 줄부터 N줄에 걸쳐 N개씩 동전들의 초기 상태가 주어진다. 각 줄에는 한 행에 놓인 N개의 동전의 상태가 왼쪽부터 차례대로 주어지는데, 앞면이 위 www.acmicpc.net Difficulty : Gold 1 Status : Solved Time : 00:39:59 문제 설명 더보기 N2개의 동전이 N행 N열을 이루어 탁자 위에 놓여 있다. 그 중 일부는 앞면(H)이 위를 향하도록 놓여 있고, 나머지는 뒷면(T)이 위를 향하도록 놓여 있다. 은 N이 3일 때의 예이다. 이들 N2개의 동전에 대하여 임의의 한 행 또는 한 열에 놓인 N개의 동전을 ..
2024.03.22 -
Problem : https://www.acmicpc.net/problem/30014 30014번: 준영이의 사랑 선린의 대표 스윗남인 준영이는 여자친구 아스나를 위한 선물을 준비 중이다. 그는 $N$개의 진주로 이루어진 원형의 진주 목걸이를 선물해 줄 생각이다. $i$ $(1 \leq i \leq N)$번째 진주알은 가치 $P_{ www.acmicpc.net Difficulty : Gold 2 Status : Solved Time : ??:??:?? 문제 설명 더보기 선린의 대표 스윗남인 준영이는 여자친구 아스나를 위한 선물을 준비 중이다. 그는 N개의 진주로 이루어진 원형의 진주 목걸이를 선물해 줄 생각이다. i(1
[백준/30014] 준영이의 사랑 (Python)Problem : https://www.acmicpc.net/problem/30014 30014번: 준영이의 사랑 선린의 대표 스윗남인 준영이는 여자친구 아스나를 위한 선물을 준비 중이다. 그는 $N$개의 진주로 이루어진 원형의 진주 목걸이를 선물해 줄 생각이다. $i$ $(1 \leq i \leq N)$번째 진주알은 가치 $P_{ www.acmicpc.net Difficulty : Gold 2 Status : Solved Time : ??:??:?? 문제 설명 더보기 선린의 대표 스윗남인 준영이는 여자친구 아스나를 위한 선물을 준비 중이다. 그는 N개의 진주로 이루어진 원형의 진주 목걸이를 선물해 줄 생각이다. i(1
2024.03.20 -
Problem : https://www.acmicpc.net/problem/31411 31411번: 대회 개최 용범이는 보라매컵에 문제를 출제하기 위해 서로 다른 $N$가지 종류의 알고리즘 문제들을 각각 $K$개씩, 총 $N\times K$개의 문제를 만들었다. 그중 $i$번째 알고리즘의 $j$번째 문제의 난이도는 $d_{ij} www.acmicpc.net Difficulty : Gold 1 Status : Solved Time : 00:18:41 문제 설명 더보기 용범이는 보라매컵에 문제를 출제하기 위해 서로 다른 N가지 종류의 알고리즘 문제들을 각각 K개씩, 총 NxK개의 문제를 만들었다. 그중 i번째 알고리즘의 j번째 문제의 난이도는 d_ij이다. 그러나 만든 문제를 모두 내기에는 대회 시간이 부족..
[백준/31411] 대회 개최 (Python)Problem : https://www.acmicpc.net/problem/31411 31411번: 대회 개최 용범이는 보라매컵에 문제를 출제하기 위해 서로 다른 $N$가지 종류의 알고리즘 문제들을 각각 $K$개씩, 총 $N\times K$개의 문제를 만들었다. 그중 $i$번째 알고리즘의 $j$번째 문제의 난이도는 $d_{ij} www.acmicpc.net Difficulty : Gold 1 Status : Solved Time : 00:18:41 문제 설명 더보기 용범이는 보라매컵에 문제를 출제하기 위해 서로 다른 N가지 종류의 알고리즘 문제들을 각각 K개씩, 총 NxK개의 문제를 만들었다. 그중 i번째 알고리즘의 j번째 문제의 난이도는 d_ij이다. 그러나 만든 문제를 모두 내기에는 대회 시간이 부족..
2024.03.02 -
Problem : https://www.acmicpc.net/problem/25241 25241번: 가희와 사직 구장 1번을 빨간색, 2번을 파란색, 3번을 검은색이라고 하였을 때 아래와 같이 배치하는 것이 최적입니다. [그림 3] 최적으로 배치한 경우 이때, 매력은 999 (1번과 2번이 인접하므로) + 333 (1번과 3번이 인 www.acmicpc.net Difficulty : Gold 1 Status : Solved Time : 01:18:24 문제 설명 더보기 가희가 응원하고 있는 롯데 자이언츠의 홈 구장인 사직 구장의 무대는 R행 C열로 이루어져 있습니다. 가희는 이 무대에 N명의 아이돌을 배치하려고 합니다. N명의 아이돌은 각각 1번부터 N번까지의 번호를 가집니다. 이 중 3명은 삼총사라고 ..
[백준/25241] 가희와 사직 구장 (Python)Problem : https://www.acmicpc.net/problem/25241 25241번: 가희와 사직 구장 1번을 빨간색, 2번을 파란색, 3번을 검은색이라고 하였을 때 아래와 같이 배치하는 것이 최적입니다. [그림 3] 최적으로 배치한 경우 이때, 매력은 999 (1번과 2번이 인접하므로) + 333 (1번과 3번이 인 www.acmicpc.net Difficulty : Gold 1 Status : Solved Time : 01:18:24 문제 설명 더보기 가희가 응원하고 있는 롯데 자이언츠의 홈 구장인 사직 구장의 무대는 R행 C열로 이루어져 있습니다. 가희는 이 무대에 N명의 아이돌을 배치하려고 합니다. N명의 아이돌은 각각 1번부터 N번까지의 번호를 가집니다. 이 중 3명은 삼총사라고 ..
2024.02.27