[백준 / C++] 1132번: 합 (그리디 알고리즘, greedy algorithm)

https://www.acmicpc.net/problem/1132 1132번: 합 N개의 수가 주어진다. 이 숫자는 모두 자연수이고, 알파벳 A부터 J가 자리수를 대신해서 쓰여 있다. 이 알파벳은 모두 한 자리를 의미한다. 그리고, 각 자리수는 정확하게 알파벳 하나이다. 0으로 www.acmicpc.net 난이도: solved.ac 골드 3 알고리즘 분류 그리디 알고리즘 접근 방법 이 문제에서 주의해야 할 점은 맨 앞자리에 위치한 알파벳은 0으로 둘 수 없다는 것이다. 일단 이 부분을 고려하지 않고 각 알파벳에 숫자를 배정하는 방법은 각 알파벳이 몇의 자리수(1, 10, 100, ...)에 위치했는지를 배열에 저장해주고 그 값이 가장 큰 알파벳 차례대로 9, 8, 7, ... 을 배정하는 것이다. 예를 ..

• format_list_bulleted PS/백준
• · 2023. 9. 26.
• textsms

[백준 / C++] 12904번: A와 B

https://www.acmicpc.net/problem/12904 12904번: A와 B 수빈이는 A와 B로만 이루어진 영어 단어가 존재한다는 사실에 놀랐다. 대표적인 예로 AB (Abdominal의 약자), BAA (양의 울음 소리), AA (용암의 종류), ABBA (스웨덴 팝 그룹)이 있다. 이런 사실에 놀란 수 www.acmicpc.net 난이도: solved.ac 골드 5 알고리즘 분류 구현, 그리디 알고리즘, 문자열 접근 방법 S에서 T로 만들려고 하지 말고, T를 S로 만들려고 하면 매우 간단해진다. 문자열을 바꿀 때는 아래의 두 가지 연산만 가능한데, 여기에 포인트가 있다. - 문자열의 뒤에 A를 붙인다. - 문자열을 뒤집고 뒤에 B를 붙인다. 결국에는 맨 뒤의 문자가 A인지 B인지만 보..

• format_list_bulleted PS/백준
• · 2023. 9. 22.
• textsms

[백준 / C++] 1461번: 도서관 (그리디 알고리즘)

https://www.acmicpc.net/problem/1461 1461번: 도서관 세준이는 도서관에서 일한다. 도서관의 개방시간이 끝나서 세준이는 사람들이 마구 놓은 책을 다시 가져다 놓아야 한다. 세준이는 현재 0에 있고, 사람들이 마구 놓은 책도 전부 0에 있다. 각 책 www.acmicpc.net 난이도: solved.ac 골드 4 알고리즘 분류 정렬, 그리디 알고리즘 접근 방법 우선 문제 조건 중 책을 모두 제자리에 놔둔 후, 즉 맨 마지막으로 옮길 때는 다시 0으로 돌아가지 않아도 된다는 조건을 빼고 생각해보자. 걸음의 수를 최소화하기 위해서는 양수에서 절댓값이 큰 것끼리 M개씩 묶어 옮기고, 음수에 절대값이 큰 것끼리 M개씩 묶어 옮기면 된다. 예제 입력 1에서는 양수: (2, 11) 음수..

• format_list_bulleted PS/백준
• · 2023. 9. 21.
• textsms

[백준 / C++] 1629번: 곱셈 (그리디 풀이...?)

https://www.acmicpc.net/problem/1629 1629번: 곱셈 첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다. www.acmicpc.net 난이도: solved.ac 실버 1 분할 정복(Divide and Conquer)을 이용해 푸신 분들이 많던데 나는 그리디(?)로 풀어보았다. A를 B번 곱하는 것은 A의 B승을 구하라는 것과 같다. 따라서 A를 A^B로 만들어주기로 했다. A는 A^1이다. A^1을 A^B로 만드는 과정은 1을 B로 만드는 과정과 같다. 우선 거듭제곱의 성질 중 a^b * a^b = a^(2b) 를 알아야 한다. 2^3 * 2^3 = 2^6 (8 * 8 = 64)을 떠올리면 이..

• format_list_bulleted PS/백준
• · 2023. 8. 14.
• textsms

[백준 / C++] 15903번: 카드 합체 놀이 (그리디, 우선순위 큐)

https://www.acmicpc.net/problem/15903 15903번: 카드 합체 놀이 첫 번째 줄에 카드의 개수를 나타내는 수 n(2 ≤ n ≤ 1,000)과 카드 합체를 몇 번 하는지를 나타내는 수 m(0 ≤ m ≤ 15×n)이 주어진다. 두 번째 줄에 맨 처음 카드의 상태를 나타내는 n개의 자연수 a1, www.acmicpc.net 난이도: solved.ac 실버 1 알고리즘 분류 그리디 알고리즘, 우선순위 큐 접근 방법 점수를 최소로 하기 위해서는 매 선택마다 가장 작은 수를 가진 카드 두 장을 선택해야 한다. 따라서 가장 작은 수가 top에 오도록 하는 우선순위 큐를 이용한다. 우선순위 큐에서 가장 작은 수 2개를 뽑아서 합친 후 그 결과를 다시 우선순위 큐에 두 번 넣으면 된다. 그..

• format_list_bulleted PS/백준
• · 2023. 7. 29.
• textsms

[백준 / C++] 17615번: 볼 모으기 (그리디 알고리즘)

https://www.acmicpc.net/problem/17615 17615번: 볼 모으기 첫 번째 줄에는 볼의 총 개수 N이 주어진다. (1 ≤ N ≤ 500,000) 다음 줄에는 볼의 색깔을 나타내는 문자 R(빨간색 볼) 또는 B(파란색 볼)가 공백 없이 주어진다. 문자열에는 R 또는 B 중 한 종류만 주 www.acmicpc.net 난이도: solved.ac 실버 1 접근 방법 결론: R과 B를 각각 맨 앞으로 옮기는 경우, 맨 뒤로 옮기는 경우 이렇게 총 4가지 경우의 수를 구해야 한다. 아래의 경우를 보자. RRRBBBRRBBRBRR R의 총 개수는 8개이고 맨 앞에 R이 3개 연속으로 있고 맨 뒤에는 R이 2개 연속으로 있다. R을 모두 맨 앞으로 몰아넣으려면 뒤에 있는 5개(전체 R의 개수..

• format_list_bulleted PS/백준
• · 2023. 7. 15.
• textsms