알고리즘/그리디12 [백준-골드4] 1744번 수 묶기 (그리디, 파이썬) https://www.acmicpc.net/problem/1744 1744번: 수 묶기 길이가 N인 수열이 주어졌을 때, 그 수열의 합을 구하려고 한다. 하지만, 그냥 그 수열의 합을 모두 더해서 구하는 것이 아니라, 수열의 두 수를 묶으려고 한다. 어떤 수를 묶으려고 할 때, 위치에 www.acmicpc.net - 입력으로 수열이 주어 졌을 때, 수 2개를 묶을 수 있다. 이 때 묶게 되면 두 값을 곱하게된다. - 모든 수는 단 한번만 묶거나, 묶지 않아야한다. 수를 적절히 묵었을 때 합의 최댓값을 구하는 문제이다. - 우선 값을 입력받으면서 0보다 큰 경우 positive 리스트에 넣었고, 0이랑 같거나 작은 경우 negative 리스트에 넣었다. - 우선 음수 수열에 대해서 최댓값을 계산했다. 두 .. 2022. 3. 14. [백준-실버4] 1049번 기타줄 (그리디, 파이썬) https://www.acmicpc.net/problem/1049 1049번: 기타줄 첫째 줄에 N과 M이 주어진다. N은 100보다 작거나 같은 자연수이고, M은 50보다 작거나 같은 자연수이다. 둘째 줄부터 M개의 줄에는 각 브랜드의 패키지 가격과 낱개의 가격이 공백으로 구분하여 주 www.acmicpc.net - N개의 기타줄이 끊어져서 다시 사야할 때, M개의 브랜드의 기타줄 가격 정보가 주어진다. - 6개 패키지 가격과 1개 낱개의 가격이 주어진다. N개의 기타줄이 필요할 때 최소 비용을 구하는 문제이다. - 처음으로 패키지 가격이 작은 순서로 정렬하였다. - ans_package는 기타줄 n개를 갈기위해 모두 패키지로 구매했을 때 가격이다. - ans_mix는 기타줄 n개를 갈기위해 n//6 .. 2022. 3. 14. [백준-실버5] 4796번 캠핑 (그리디, 파이썬) https://www.acmicpc.net/problem/4796 4796번: 캠핑 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있고, L, P, V를 순서대로 포함하고 있다. 모든 입력 정수는 int범위이다. 마지막 줄에는 0이 3개 주어진다. www.acmicpc.net - 연속하는 P일중 L일동안 캠핑 할 수 있을 때, 강산이가 휴가를 V일 받았다. 이 때 최대 캠핑가능한 일수를 구하는 문제 - 강산이가 최대로 캠핑할 수 있는 날짜는 우선 (V//P)*L일이 가능하다. - 여기에 추가해야할 부분이 나머지 일수에 대한 V%P일이다. - 이 때 V%P가 L일 보다 큰 경우, 남은 일 수 중 L일 만큼 더 캠핑 할 수 있다. - V %P가 L일 보다 작은 경우는.. 2022. 3. 14. [백준-실버5] 1439번 뒤집기 (그리디, 파이썬) https://www.acmicpc.net/problem/1439 1439번: 뒤집기 다솜이는 0과 1로만 이루어진 문자열 S를 가지고 있다. 다솜이는 이 문자열 S에 있는 모든 숫자를 전부 같게 만들려고 한다. 다솜이가 할 수 있는 행동은 S에서 연속된 하나 이상의 숫자를 잡고 모 www.acmicpc.net - 문자열이 0과 1로만 주어졌을 때, 연속 되는 수는 뒤집을 수 있다. 이 때 모두 같은 수로 만들기 위해 최소 몇번의 뒤집기를 실행해야하는지 찾는 문제이다. - 나는 입력받은 문자열을 zero_list에 '0'을 기준으로 스플릿하고, one_list에는 '1'을 기준으로 스플릿했다. -> 연속되는 숫자를 뒤집을 수 있기 때문 - 그리고 각각의 리스트를 순회하면서 갯수를 파악해서 zero_cnt.. 2022. 3. 13. 이전 1 2 3 다음