[백준 / 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++] 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

[백준 / C언어] 1080번: 행렬

https://www.acmicpc.net/problem/1080 1080번: 행렬 첫째 줄에 행렬의 크기 N M이 주어진다. N과 M은 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 행렬 A가 주어지고, 그 다음줄부터 N개의 줄에는 행렬 B가 주어진다. www.acmicpc.net 난이도: solved.ac 실버 1 (주의해야할 점) 행렬을 입력받을 때 1 1 0 0 1 0 0 1 0 처럼 한 칸씩 띄어져 있는게 아니라 110 010 010 처럼 붙여있는 형태라 "%1d"로 입력받아야 숫자 하나당 scanf를 할 수 있다 행렬의 크기가 3*3보다 작을 때는 무조건 -1를 출력하는 게 아니라 두 행렬이 같을 때는 0을 출력한다 #define _CRT_SECURE_NO_WARNINGS #in..

• format_list_bulleted PS/백준
• · 2023. 5. 17.
• textsms