목록그리디 알고리즘 (41)

1일1알

백준 2374번 같은 수로 만들기 C++

가장 작은 수부터 인접한 수와 같게 만들어가면서 문제를 해결하였다. 답을 int로 하면 오버플로우가 나기 때문에 long long을 사용하였다. #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; using ll = long long; int n; vector v(1001); ll ans = 0; void Add(int index) { int val = v[index]; int start = index; int end = index; int MIN = 1000000001; while (true) ..
알고리즘 2022. 2. 9. 13:05
백준 2777번 숫자 놀이 C++

한 자리수 중 가장 큰 수인 9부터 2까지의 곱으로 나타낼 수 있는지 확인하고 가능하다면 그 개수를 출력하고, 가능하지 않다면 -1을 출력한다. 1은 따로 처리해 주었다. #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; using ll = long long; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int t, n; cin >> t; while (t--) { cin >> n; if (n == 1) { cout
알고리즘 2022. 1. 29. 15:47
백준 8980번 택배 C++

1. 도착지점을 기준으로 오름차순 정렬을 한다. 도착지점이 같을 경우에는 시작지점을 기준으로 오름차순 정렬을 한다. (시작지점을 기준으로 정렬을 하면 독점이 일어날 수 있다.) 2. 각 지점마다 트럭의 용량을 저장하는 벡터를 만들고, 시작지점에서 도착지점까지 중 가장 트럭에 짐이 많이 실린 용량 을 찾는다. 3. 트럭의 짐의 용량 + 내 용량이 c보다 크면 짐을 실을 수 있는 만큼만 자른다. 4. 시작지점부터 도착지점까지 내 짐의 무게가 트럭에 더해진다. 5. 2~4를 m만큼 반복한다. #include #include #include #include #include #include #include #include #include #include #include #include #include using ..
알고리즘 2022. 1. 28. 14:18
백준 1083번 소트 C++

1. 배열을 탐색하면서 가장 큰 값을 찾는데, 순회 도중 인덱스가 s를 넘어가면 탐색을 중지한다. (인덱스가 s를 넘어서는 가장 큰 값을 찾았다고 해도 인덱스만큼 옮길 수 없기 때문에 그 수를 맨 앞으로 옮길 수 없다.) 2. 찾은 수는 맨 앞으로 옮길 수 있는 수 중에서 가장 큰 수이다. 맨 앞으로 옮기면 그 위치에 고정될 것이고, 앞으로 옮기는 데에 비용이 들기 때문에 배열에서 찾은 수를 지우고 새로운 벡터에 찾은 수를 넣는다. 3. 이론상으로는 앞으로 옮긴 것이기 때문에 s에서 찾은 수의 인덱스를 빼준다. 4. s가 0이 되거나 이미 모든 수가 정렬이 되어있으면 앞에서부터 차례대로 2에서 만든 벡터에 값을 넣어준다. 5. 새로운 벡터의 원소들을 출력한다. #include #include #inclu..
알고리즘 2022. 1. 27. 12:40
백준 1092번 배 C++

1. 크레인과 박스들을 내림차순으로 정렬한다. 2. 맨 앞의 박스가 크레인이 감당할 수 있는 무게보다 무거우면 옮길수 없으므로 1을 출력하고 프로그램을 종료한다. 3. 박스가 전부 빌 때까지 크레인을 순회하면서 박스를 순회하면서 (2중 for문) 박스를 담을 수 있으면 박스의 벡터에 erase를 통해 박스를 지워준다. (크레인 한 번 순회하면 cnt++) 위에처럼 풀어도 풀리긴 하지만 박스를 지우는 erase가 시간이 오래 걸린다. 크레인이 500개만 되어도 시간초과가 날 것이다. 그래서 erase를 사용하지 않고 visited를 이용해 이미 담은 것인지를 판별하도록 코드를 수정하였다. #include #include #include #include #include #include #include #in..
알고리즘 2022. 1. 26. 13:05
백준 1474번 밑 줄 C++

_의 개수의 최대값과 최솟값의 차이는 1이 되어야 하기 때문에 가능한 밑줄의 종류는 두 가지이다. 1. 주어진 문자열과 m을 이용하여 짧은 밑줄에 _가 몇 개 들어가는지와 총 짧은 밑줄의 개수를 구한다. 2. 1과 마찬가지로 긴 밑줄에 _가 몇 개 들어가는지와 총 긴 밑줄의 개수를 구한다. 3. 문자열을 차례대로 보면서 맨 앞이 a~z일 경우 긴 밑줄의 개수가 1 이상이면 긴 밑줄을 붙이고 긴 밑줄의 개수를 1 줄인다. 4. 맨 앞이 A ~ Z일 경우 짧은 밑줄의 개수가 1 이상이면 짧은 밑줄을 붙이고 짧은 밑줄의 개수를 1 줄인다. 5. 3,4 조건만 있을 경우 모든 문자열의 첫 글자가 A~Z이면 짧은 밑줄만 쓰기 때문에 남은 짧은 밑줄의 개수가 없을 경우에는 긴 밑줄을 붙인다. #include #in..
알고리즘 2022. 1. 25. 19:28
이전 Prev 1 ··· 3 4 5 6 7 Next 다음