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

1일1알

백준 1339번 단어 수학 C++

알파벳이 앞에 나올수록 가산점을 더 부여해서 알파벳의 개수를 저장하고 저장한 알파벳의 개수가 많은 순서대로 숫자를 할당하였다. 예를들어 AA, BC 가 있다면 A는 10 + 1 = 11, B는 10, C는 1이 되고 A에 9, B에 8, C에 7을 할당한다. 만약 알파벳의 길이가 다르다면 가장 긴 알파벳의 개수를 기준으로 짧은 알파벳 앞에 @를 더해서 건너뛰도록 하였다. 예를들어 ABC, DE가 있다면 DE앞에 @를 붙여 @DE로 만들어서 길이를 맞춰주고 @인 경우는 연산을 하지 않도록 했다. #include #include #include #include #include #include #include #include #include #include #include #include #include #i..
알고리즘 2022. 8. 12. 17:02
백준 1715번 카드 정렬하기 C++

작은거끼리 먼저 합칠수록 비교 횟수가 적어지기 때문에 우선순위 큐를 이용하여 제일 작은게 먼저 나오도록 해서 문제를 풀었다. #include #include #include #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); priority_queue pq; int n; cin >> n; for (int i = 0; i < n; i++)..
알고리즘 2022. 6. 7. 12:42
백준 1817번 짐 챙기는 숌 C++

#include #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 n, m; cin >> n >> m; int cnt = 0; int weight = m; for (int i = 0; i > book; if (weight + book > m) { cnt++; weight = boo..
알고리즘 2022. 5. 6. 15:59
백준 1417번 국회의원 선거 C++

우선순위 큐를 이용하였다. #include #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); priority_queue pq; int n; int dasom; int cnt = 0; cin >> n; cin >> dasom; for (int i = 1; i > vote; pq.push(v..
알고리즘 2022. 4. 28. 13:59
백준 1213번 팰린드롬 만들기 C++

우선 홀수개인 알파벳의 개수가 2개 이상이면 팰린드롬을 만들 수 없기 때문에 이 경우에는 바로 "I'm Sorry Hansoo" 를 출력한다. 그리고 홀수개인 알파벳의 개수가 한개라면 이 경우에서는 알파벳이 n/2 , 1, n/2 로 나눠지고 나머지의 경우에는 알파벳이 n/2, n/2 로 나눠진다. 사전순서대로 저장해주는 map 를 이용해 알파벳들을 저장하고 순회하면서 n/2만큼을 출력할 문자열에 붙여주고 남은 n/2는 스택에 넣어둔다. 그리고 홀수개인 알파벳이 하나가 있다면 n/2, 1, n/2의 중간의 1개의 알파벳을 저장해둔다. 홀수개인 알파벳이 있었다면 저장해둔 1개의 알파벳을 붙여두고 스택에서 빼가면서 출력할 문자열에 붙여준다. ex) AABBCCCCC - A : 2개, B : 2개, C : 5..
알고리즘 2022. 4. 15. 11:07
백준 12904번 A와 B C++

처음에는 S에서 백트래킹을 해서 T로 가는 방법을 생각해봤는데 범위를 보니 무조건 시간초과가 날 것 같아서 다른 방법을 생각해 보았다. T에서 S로 거꾸로 거슬러 올라가는 방법으로 문제를 해결하였다. T의 맨 뒤가 A라면 그냥 A를 빼고 T의 맨 뒤가 B라면 B를 빼고 문자열을 뒤집어준다. 이걸 반복하다가 S와 길이가 같아졌을 때 S와 T가 일치하면 S로 T를 만들 수 있는 것이고, 일치하지 않는다면 만들 수 없는 것이다. #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; using ll = l..
알고리즘 2022. 3. 18. 11:19
이전 Prev 1 2 3 4 5 6 7 Next 다음