🔗문제 보러가기 12904번: A와 B 수빈이는 A와 B로만 이루어진 영어 단어가 존재한다는 사실에 놀랐다. 대표적인 예로 AB (Abdominal의 약자), BAA (양의 울음 소리), AA (용암의 종류), ABBA (스웨덴 팝 그룹)이 있다. 이런 사실에 놀란 수 www.acmicpc.net 👨‍💻풀이 과정 그리디 방식으로도 풀 수 있다고 하길래, 어떻게 하는지 궁금해서 관련 🔗힌트 글을 찾아봤습니다. 이런 생각을 할 수 있다니... 대단하네요. 세상에는 천재가 너무 많습니다. 기존 문자열인 S에서 목표로 하는 문자열 T로 변환하는 경우의 수는 너무 많은데 비해, 그 경우의 수가 다 올바른 길도 아닙니다. 그렇기에, T에서 S로 반대로 변환하는 것이 아이디어더군요. T에서 S로 변환해 나가는 과정은..

🔗문제 보러가기 14891번: 톱니바퀴 첫째 줄에 1번 톱니바퀴의 상태, 둘째 줄에 2번 톱니바퀴의 상태, 셋째 줄에 3번 톱니바퀴의 상태, 넷째 줄에 4번 톱니바퀴의 상태가 주어진다. 상태는 8개의 정수로 이루어져 있고, 12시방향부터 www.acmicpc.net 👨‍💻풀이 과정 톱니바퀴를 시계 혹은 반시계 방향으로 회전시키는 기능과 양 옆 톱니바퀴와 맞물린 이빨의 자석 극이 서로 다를 경우, 해당 톱니바퀴들 또한 재귀적으로 회전시켜주는 것이 핵심입니다. 이걸 어떻게 구현했는지 한 단계씩 차례대로 살펴보겠습니다. 우선 1번부터 4번 톱니바퀴의 각 이빨의 극 정보를 배열에다가 저장해줍니다. #define GEARWHELL_COUNT 4 vector gearWheels(GEARWHELL_COUNT + 1)..

🔗문제 보러가기 2636번: 치즈 첫째 줄에는 사각형 모양 판의 세로와 가로의 길이가 양의 정수로 주어진다. 세로와 가로의 길이는 최대 100이다. 판의 각 가로줄의 모양이 윗 줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진 www.acmicpc.net 👨‍💻풀이 과정 구현 문제는 요구 사항이 많기 때문에, 구현해야 할 기능별로 함수화하여 접근하는 게 가장 좋은 것 같습니다. 이 문제에서 구현해야 할 요구사항들은 다음과 같습니다. 1. 문제에서 주어진 입력을 받는 함수 문제에서 가로 행의 개수와 세로 행의 개수, 그리고 판의 상태를 입력으로 줍니다. 이러한 내용들을 배열에 입력받되, 치즈의 개수 또한 세서 별도의 변수에 저장해주었습니다. 이 치즈의 개수가 루프 종료 조건이기 때문이죠. 2. 공기를 주변으..

🔗문제 보러가기 14499번: 주사위 굴리기 첫째 줄에 지도의 세로 크기 N, 가로 크기 M (1 ≤ N, M ≤ 20), 주사위를 놓은 곳의 좌표 x, y(0 ≤ x ≤ N-1, 0 ≤ y ≤ M-1), 그리고 명령의 개수 K (1 ≤ K ≤ 1,000)가 주어진다. 둘째 줄부터 N개의 줄에 지 www.acmicpc.net 👨‍💻풀이 과정 일종의 공간지각능력(?)을 필요로 하는 구현 문제입니다. 초기에 주어진 주사위 상태에서 동, 서, 남, 북 방향으로 구르면 그에 따라 주사위 면에 적힌 숫자를 잘 정리하는 절차가 필요하죠. 그래서 저는 6개의 원소를 가지는 1차원 배열에다가 주사위의 각 면에 적힌 숫자 정보를 관리했습니다. enum DIRECTION { TOP, RIGHT, LEFT, FORWARD,..

🔗문제 보러가기 14725번: 개미굴 첫 번째 줄은 로봇 개미가 각 층을 따라 내려오면서 알게 된 먹이의 정보 개수 N (1 ≤ N ≤ 1000)개가 주어진다. 두 번째 줄부터 N+1 번째 줄까지, 각 줄의 시작은 로봇 개미 한마리가 보내준 먹이 정 www.acmicpc.net 👨‍💻풀이 과정 메이플스토리 개미굴이 생각나는 문제였습니다. 트라이(Trie) 자료구조를 활용해서 풀 수 있었는데, 트라이와 관련된 코드를 작성하는 게 익숙하지 않아 조금 오래 걸렸습니다. 같은 층에 여러 개의 방이 있을 경우에는 사전순으로 먹이 정보를 출력해야 하기에 map을 활용하여 트라이를 구현하였습니다. class Trie { public: Trie(int depth) : depth(depth) { } ~Trie(); vo..

🔗문제 보러가기 1644번: 소수의 연속합 첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 4,000,000) www.acmicpc.net 👨‍💻풀이 과정 2부터 N까지 소수를 구하는 "에라토스테네스의 체" 알고리즘 1번에서 구한 소수들의 누적합을 저장해 둔 배열 투 포인터를 사용하여 부분 구간을 이동해가며, N이 나오는 구간의 개수를 카운트 위 순서대로 저는 문제를 풀었습니다. 투 포인터와 관련된 소스 코드는 많이 작성해보지 않아서 그런지, 짜는 데에 조금 시간이 걸리네요. ✏️소스 코드 및 결과 #include #include using namespace std; #define FAST_IO ios::sync_with_stdio(false); cout.tie(NULL); cin.tie(NULL); ..

🔗문제 보러가기 13904번: 과제 예제에서 다섯 번째, 네 번째, 두 번째, 첫 번째, 일곱 번째 과제 순으로 수행하고, 세 번째, 여섯 번째 과제를 포기하면 185점을 얻을 수 있다. www.acmicpc.net 👨‍💻풀이 과정 과제 마감일을 기준으로 오름차순 정렬을 하되, 마감일이 같다면 점수가 높은 순으로 정렬해줍니다. 경과된 날짜 변수를 0으로 세팅하고, 주어진 과제들을 순회합니다. 기간 내에 가능한 숙제라면, 과제를 진행합니다. (경과된 날짜 변수 + 1) 마감일이 지났고 이미 완료한 과제들 중에 가장 낮은 점수보다 점수를 적게 준다면, 다음 과제를 확인합니다. 이미 완료한 과제들이 항상 점수를 기준으로 오름차순 정렬이 되어 있도록, 우선순위 큐를 사용합니다. 마지막 과제까지 확인을 했는데도 ..

🔗문제 보러가기 2638번: 치즈 첫째 줄에는 모눈종이의 크기를 나타내는 두 개의 정수 N, M (5 ≤ N, M ≤ 100)이 주어진다. 그 다음 N개의 줄에는 모눈종이 위의 격자에 치즈가 있는 부분은 1로 표시되고, 치즈가 없는 부분은 0으로 www.acmicpc.net 👨‍💻풀이 과정 내부 공기와 외부 공기를 어떻게 구별할까 고민했습니다. 문득 떠오른 생각은 다각형 외부 내부 판별 알고리즘이었는데, 치즈가 다각형이 아닐 수도 있기 때문에 적용할 수가 없더라구요. 그래서 문제에서 주어진 정보인, "가장자리에는 치즈가 놓이지 않는다"라는 걸 활용해 가장자리에서부터 BFS를 통해 외부 공기를 만들어주기로 결정하였습니다. 이 로직을 위해, 입력 세팅을 할 때 조금 다르게 세팅해주었습니다. // 전역 변수들..