본문 바로가기

Algorithm/Greedy

 (43)
(C++) - 백준(BOJ) 2891 : 카약과 강풍 https://www.acmicpc.net/problem/2891 2891번: 카약과 강풍 첫째 줄에 팀의 수 N, 카약이 손상된 팀의 수 S, 카약을 하나 더 가져온 팀의 수 R이 주어진다. (2 ≤ N ≤ 10, 1 ≤ S, R ≤ N) 둘째 줄에는 카약이 손상된 팀의 번호가 주어진다. 팀 번호는 중복되지 않 www.acmicpc.net greedy 문제였습니다. 📕 풀이방법 📔 입력 및 초기화 전체 팀 수 n, 카약이 부러진 팀 수 s, 여분 카약 가진 팀 수 r, 팀별 보유 현황 일차원 배열 kayak, 정답을 출력할 변수 ans를 선언 후 입력받습니다.* 카약의 여분이 있으나 부러질 수 있음을 고려해야 합니다. 따라서 처음 kayak을 1로 초기화 한 후 부러졌다면 1을, 여분이 있다면 1을 더..
(C++) - 백준(BOJ) 17509 : And the Winner Is... Ourselves! https://www.acmicpc.net/problem/17509 17509번: And the Winner Is... Ourselves! 11 lines are given as the input. The $i$-th line contains two space-separated integers, $D_i$ and $V_i$, where $D_i$ is the amount of minutes required to solve the $i$-th problem, and $V_i$ is the number of incorrect verdicts on the $i$-th problem. For eac www.acmicpc.net greedy문제였습니다. 📕 풀이방법 📔 입력 및 초기화 정답을 출력할 penalty..
(C++) - 백준(BOJ) 11256 : 사탕 https://www.acmicpc.net/problem/11256 11256번: 사탕 당신은 사탕 공장의 주인이다. 날마다, 당신은 J개의 사탕을 가게에 보내기 위해 상자에 포장해야 한다. 당신은 크기가 다른 상자 N개를 가지고 있다. 당신은 편리를 위해 상자를 최소한으로 쓰 www.acmicpc.net greedy문제였습니다. 📕 풀이방법 📔 입력 및 초기화 testcase, 사탕 수 candyNum, box 수 boxNum, sum, cnt, 상자를 입력받을 vector boxes를 선언 후 입력받습니다. 📔 풀이과정 1. boxes를 가로 * 세로가 큰 순으로 정렬해줍니다.2. 필요한 상자의 개수가 최소여야하므로 최대한 사탕을 담는것이 유리합니다. 가로 * 세로가 곧 사탕의 개수이므로 for lo..
(C++) - 백준(BOJ) 16208 : 귀찮음 https://www.acmicpc.net/problem/16208 16208번: 귀찮음 현우는 무슨 이유에선지 길이 a1, ..., an의, 총 n개의 쇠막대가 필요해졌다. 하지만 그가 가진 것은 길이 a1+...+an의 하나의 쇠막대뿐이었다. 현우는 이 막대를 직접 잘라서 원래 필요하던 n개의 쇠 www.acmicpc.net 간단한 greedy 문제였습니다. 📕 풀이방법 📔 입력 및 초기화 수의 개수 n, 필요한 막대의 길이를 저장할 length, 정답을 출력할 ans, 필요 막대들의 정보를 입력받을 vector v를 선언 후 입력받습니다. 📔 풀이과정 n개의 막대들의 총 길이를 length에 저장합니다. 어떤 방법을 사용해도 결국에는 length길이의 막대를 n-1번 잘라야 합니다. 결국에는 x*y..
(C++) - 백준(BOJ) 13416 : 주식투자 https://www.acmicpc.net/problem/13416 13416번: 주식 투자 입력 데이터는 표준 입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫째 줄에는 테스트 케이스의 개수를 나타내는 자연수 T가 주어진다. 각각의 테스트 케이스의 첫째 줄에 www.acmicpc.net greedy문제였습니다. 📕 풀이방법 📔 입력 및 초기화 test case 수 t, 주식 일 수 n, 정답을 출력할 변수 ans를 선언한 후 적절히 입력받습니다. 📔 풀이과정 1. n만큼 for loop를 수행하며 A,B,C사의 이익과 손해 data를 변수 a,b,c를 선언해 입력해줍니다.2. 지역변수 profit을 선언해 a,b,c중 최댓값을 저장해줍니다.3. profit이 음수라면 무조건 손해이기..
(C++) - 백준(BOJ) 16435 : 스네이크버드 https://www.acmicpc.net/problem/16435 16435번: 스네이크버드 첫 번째 줄에 과일의 개수 N (1 ≤ N ≤ 1,000) 과 스네이크버드의 초기 길이 정수 L (1 ≤ L ≤ 10,000) 이 주어집니다. 두 번째 줄에는 정수 h1, h2, ..., hN (1 ≤ hi ≤ 10,000) 이 주어집니다. www.acmicpc.net greedy로 푼 문제였습니다. 📕 풀이방법 📔 입력 및 초기화 처음 스네이크버드의 길이 snakeBirdLength, 과일 개수 n, n개의 과일 높이 정보를 저장할 vector fruitHeight를 선언 한 후 적절히 입력받습니다. 📔 풀이과정 새가 제일 길어지려면 과일을 최대한 많이 먹어야 합니다. 이를 위해 과일 높이를 오름차순으로 정렬..
(C++) - 백준(BOJ) 9237 : 이장님 초대 https://www.acmicpc.net/problem/9237 9237번: 이장님 초대 입력은 두 줄로 이루어져 있다. 첫째 줄에는 묘목의 수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄에는 각 나무가 다 자라는데 며칠이 걸리는지를 나타낸 ti가 주어진다. (1 ≤ ti ≤ 1,000,000) www.acmicpc.net greedy문제였습니다. 📕 풀이방법 📔 입력 및 초기화 묘목의 수 n, 이장님 만나는 날 meetDay, 묘목 자라는데 걸리는 시간을 저장할 vector형 변수 growDay를 선언 후 적절히 입력해줍니다. 📔 풀이과정 자라는데 오래걸리는 묘목은 최대한 빨리 심어야 합니다. 따라서 growDay를 내림차순으로 정렬해줍니다.1. growDay에 대해 for loop를 수..
(C++) - 백준(BOJ) 1388 : 바닥 장식 https://www.acmicpc.net/problem/1388 1388번: 바닥 장식 형택이는 건축가이다. 지금 막 형택이는 형택이의 남자 친구 기훈이의 집을 막 완성시켰다. 형택이는 기훈이 방의 바닥 장식을 디자인했고, 이제 몇 개의 나무 판자가 필요한지 궁금해졌다. 나 www.acmicpc.net greedy로 푼 문제였습니다. 📕 풀이방법 📔 입력 및 초기화 n행 m열을 선언 후 입력한 다음 이차원 배열 room에 n행 m열만큼 구조를 입력해줍니다. 체크 배열 ck도 선언해줍니다. 📔 풀이과정 0행 0열부터 시작해 체크가 안되어있으면 다음을 수행합니다. 1. 체크가 안된 위치가 i행 j열인 경우 ans++ 후 그 값을 변수 shape에 저장합니다. 2. shape이 '-'라면 '|'가 나오기 전..

티스토리툴바