본문 바로가기

728x90
반응형
SMALL

백준 write-up/정렬 & 그리디

(84)
[백준] 거스름돈 : 14916번 - Python https://www.acmicpc.net/problem/14916 14916번: 거스름돈 첫째 줄에 거스름돈 액수 n(1 ≤ n ≤ 100,000)이 주어진다. www.acmicpc.net 문제를 풀면서 몰랐던 개념 - 어떤 계산의 몫이 3이라고 하자. 그 몫에서 1을 빼주어서 2로 만들어주고 싶을 때는 나머지에 나누는 수를 더해주면 됨. ex) n // 5 = 3 3 -> 2 로 취급해서 계산을 하고 싶다면, (n % 5)에 + 5 를 해주기! 문제의 접근 방법 - 거스름돈이 1과 3일 경우에는 5와 2 모두로 나누어 떨어질 수 없기 때문에 계산 불가하다. 따라서 -1을 출력해주어야 함. - 거스름돈이 5로 나누었을 때의 나머지가 짝수이면, 2로 나눌 수 있다는 것이므로 5로 먼저 나눠준 후(최대 횟..
[백준] 포인트 카드 : 14471번 - Python https://www.acmicpc.net/problem/14471 14471번: 포인트 카드 예제 입출력 1에서, 포인트 카드 1의 꽝 도장 3개와 포인트 카드 3의 꽝 도장 1개를 당첨 도장으로 바꾸면, 4엔으로 5-1=4장의 카드가 경품과 교환 가능하게 되어, 이것이 최소 비용이다. 예제 입출 www.acmicpc.net 문제의 접근 방법 - 내림차순 정렬 - 이미 당첨 도장의 개수가 M보다 큰 A값을 제외한 나머지 경우의 수만 생각하기 나머지 경우의 수가 M-1이 될 때까지 계산. - 경품의 개수가 충족이 되지 않아서 도장을 바꿔야할 때 내는 1엔이 비용에 들어감. - 최소 비용을 구해야 하기 때문에 M-1에서 M보다 작은 A값들의 개수를 빼준 횟수만큼만 반복문을 돌려서 바꿔야 할 도장의 개수(1..
[백준] 에너지 드링크 : 20115번 - Python https://www.acmicpc.net/problem/20115 20115번: 에너지 드링크 페인은 에너지 드링크를 좋아하는 회사원이다. 에너지 드링크는 카페인, 아르기닌, 타우린, 나이아신 등의 성분이 들어있어 피로 회복에 도움을 주는 에너지 보충 음료수이다. 야근을 마치고 한 www.acmicpc.net 문제의 접근 방법 - 합쳐진 에너지 드링크의 양을 최대로 하기 위해 입력된 에너지 드링크의 양을 내림차순으로 정렬하기 - 임의의 서로 다른 두 에너지 드링크를 고를 때, 두 개 중 더 양이 적은 에너지 드링크를 버리기 - 작은 숫자들을 이용해서 여러 조합을 그려보기 =>> 큰 수부터 나열해야 함을 알 수 있음 내가 막혔던 부분 - 아이디어는 생각했지만 코드로 구현하는 과정에서 시간이 조금 소요됨...
[백준] 책 정리 : 1434번 - Python https://www.acmicpc.net/problem/1434 1434번: 책 정리 첫째 줄에 박스의 개수 N, 책의 개수 M이 주어진다. 둘째 줄에는 박스의 용량 A1, A2, ..., AN이 주어지고, 셋째 줄에는 B1, B2, ..., BM이 주어진다. www.acmicpc.net 문제를 풀면서 몰랐던 개념 [Python] append 함수와 extend 함수의 차이 : list.append(x)는 리스트 끝에 x 한 개를 그대로 넣는다면 list.extend(iterable)은 리스트 끝에 가장 바깥쪽 iterable의 모든 항목을 넣는다. # B가 리스트형일 때 A = ['one2ye', 'loves', '20s'] B = ['me', 'too'] A.append(B)# append 함수 p..
[백준] 모두의 마블 : 12845번 - Python https://www.acmicpc.net/problem/12845 12845번: 모두의 마블 영관이는 게임을 좋아한다. 별의별 게임을 다 하지만 그 중에서 제일 좋아하는 게임은 모두의 마블이다. 어김없이 오늘도 영관이는 학교 가는 버스에서 캐릭터 합성 이벤트를 참여했다. 이번 이 www.acmicpc.net 문제의 접근 방법 - 카드를 합치는 과정에 대해 그림을 그려서 표현해보기 - 가장 처음에 카드를 합칠 때 레벨이 제일 높은 카드에 합쳐야 골드의 값이 최대가 될 수 있음. ---> 2번과 같은 방식으로 카드를 합쳐야 최대 골드를 획득할 수 있다! 그림을 그려놓고 보니 1번과 2번의 가장 큰 차이점이 처음에 합친 카드의 레벨이라는 것을 알 수 있었다. 합성할 수 있는 두 카드 A,B는 늘 인접해야 하..
[백준] 팬덤이 넘쳐흘러 : 17262번 - Python https://www.acmicpc.net/problem/17262 17262번: 팬덤이 넘쳐흘러 선물 포장 공장을 말아먹은 욱제는 계곡에서 백숙을 파느라 학교에 자주 가지 못한다. 하지만 월클의 인생은 피곤한 법! 욱제는 지금처럼 힘든 시기에도 자신을 기다리는 5조5억명의 열렬한 팬 www.acmicpc.net 문제의 접근 방법 - N명의 팬들이 머무는 시간을 의미하는 입력 값 s,e 중에서 가장 큰 값(max)에서 가장 작은 값(min)을 빼면 욱제가 학교에 머물러야 할 시간을 구할 수 있음. 여기서 가장 큰 값은 제일 늦게 등교한 학생을 의미하고, 가장 작은 값은 제일 빨리 하교한 학생을 의미한다! - 팬들이 머무르는 시간이 모두 겹치면(=위의 계산 결과 값이 음수이면) 욱제가 학교에 머물러야 할 ..
[백준] 욱제는 도박쟁이야!! : 14655번 - Python https://www.acmicpc.net/problem/14655 14655번: 욱제는 도박쟁이야!! 첫째 줄에 동전의 수 N이 주어진다. (1 ≤ N ≤ 10,000) 둘째 줄에 욱제의 첫 번째 라운드의 N개 동전의 배열이 주어진다. 셋째 줄에 욱제의 두 번째 라운드의 N개 동전의 배열이 주어진다. 동전에 적 www.acmicpc.net 문제의 접근 방법 - 획득한 점수가 최대가 되려면 1라운드에서는 최댓값을 구해야하고 2라운드에서는 최솟값을 구해야 함. - 1라운드: 모두 양수로 만들어주면 됨 / 2라운드: 모두 음수로 만들어주면 됨 (1라운드 동전들의 합 - 2라운드 동전들의 합) = 1,2라운드 동전들에 적힌 숫자의 절댓값들의 합 - 동전을 뒤집을 수 있는 횟수가 무제한이라는 점 유념하기 내가 ..
[백준] 동전 뒤집기 : 1285번 - Python https://www.acmicpc.net/problem/1285 1285번: 동전 뒤집기 첫째 줄에 20이하의 자연수 N이 주어진다. 둘째 줄부터 N줄에 걸쳐 N개씩 동전들의 초기 상태가 주어진다. 각 줄에는 한 행에 놓인 N개의 동전의 상태가 왼쪽부터 차례대로 주어지는데, 앞면이 위 www.acmicpc.net 문제를 풀면서 몰랐던 개념 (1) [Python] 비트 마스크(bitmask) : 정수를 이진수로 표현하여 비트 연산을 통해 문제를 해결해 나가는 기술 -> 이를 활용해 DP가 가능함! AND : & OR : | XOR : ^ NOT : ~ Shift : > ex) 13(1101)을 오른쪽으로 1bit 움직인다고 하면, 6(0110)이 됨. (2) [Python] 진법 변환 : 10진수 -> ..

728x90
반응형
LIST