반응형 🤓 스터디17 [ 백준 BOJ / c++ ] 3085번 사탕게임 🤔 문제 링크 : https://www.acmicpc.net/problem/3085👀 접근 방식우선 아래와 같이 접근하였다.사탕교환시 인덱스 범위를 초과하는 것을 막기위해 패딩 1을 더한 크기 52*52의 배열을 만든다.입력된 각 문자에 대해 상하좌우 각각 이동시 먹을 수 있는 최대 사탕수를 계산한다.최대가 되는 사탕값을 저장한다.문제를 처음 보았을때, 사탕이 교환 즉, 배열 값들이 이동하여야하기 때문에 따로 if문을 추가해 예외처리하기 번거로울 것 같아 패딩을 추가하는 것을 먼저 생각하였다. 아래와 같이 패딩을 추가해 교환시에도 인덱스 오류가 발생 위험을 없앴다. 또한, 최대 개수를 검사할때는 패딩을 제외한 영역을 검사하여, 연속된 패딩 값이 최대값이 되는것을 방지하였다.마지막으로, 연속된 사탕의.. 2025. 2. 4. [ 백준 BOJ / c++ ] 5397번 키로거 🤔 문제 링크 : https://www.acmicpc.net/problem/5397 👀 접근 방식2개의 스택을 활용해 "" , "-" 문자에 대한 명령을 아래와 같이 수행하는 것으로 방향을 잡았다.' 일때, 스택1의 top값을 스택2로 옮긴다. ( 스택1이 비어있지 않을시 )'>' 일때, 스택2의 top값을 스택1로 옮긴다. ( 스택2이 비어있지 않을시 )'-' 일때, 스택1의 top값을 pop을 사용해 제거한다. ( 스택1이 비어있지 않을시 )이후 각 스택에 담긴 문자를 문자열로 바꾸는 작업을 진행한다. 이때 스택1의 문자는 reverse함수를 사용에 뒤집어 주었다.💻 코드#include #include #include #include#includeusing namespace std;void p.. 2025. 2. 3. [ 백준 BOJ / c++ ] 10971번 외판원 순회 2 🤔 문제 링크 : https://www.acmicpc.net/problem/10971👀 접근 방식먼저, 다음과 같이 설계하였다.모든 노드의 비중복 선택 경우의 수 를 계산마지막으로 선택된 노드에서 시작 노드로 돌아갈 가중치를 더해 최소값 찾기1번 같은 경우, 백트래킹을 사용해 비중복 경우의 수를 구하였다.2번은 백트래킹이 끝나는 시점에 ( 시작노드 비용 ~ 마지막 노드 비용 ) 순으로 비용을 더한후 마지막 노드에서 시작노드로 돌아갈시 생기는 비용을 더해 순환 시 발생하는 총 비용 계산후 min함수를 통해 최솟값을 업데이트 하였다. 추가로, 처음 제출시 오답이였는데, 이는 갈 수 없는 곳은 0으로 처리하기 때문이다. 즉, 다음과 같이 입력되면 0이 입력된 4행의 2번째 값을 알고리즘이 비용이 0인것으로.. 2025. 2. 2. [ 백준 BOJ / c++ ] 15663번 N과 M (9) 🤔 문제 링크 : https://www.acmicpc.net/problem/15663 👀 접근 방식모든 경우의 조합을 생각하되, 오름차순 정렬 및 중복 출력X 를 고려해야 한다. 조합 및 순열을 만드는 방법으로는 "백트래킹"을 사용하도록 한다. "오름차순 정렬"의 경우 백트래킹을 진행하기 전 입력값을 오름차순으로 정렬 후 진행하면 낮은 값 ~ 높은 값 순으로 출력이 되기 때문에 함수 실행 전 sort함수를 사용해 미리 오름차순 정렬을 진행한다. "중복 출력 방지"의 경우 다음 입력값을 최근 조합의 마지막 값과 같은지 검사해, 같지 않을 경우 다음 백트래킹을 진행하면 된다. 예를 들어, 이전 조합의 "2 4" 이고 다음 숫자가 4인 경우 조합 "2 4"의 마지막 값인 4와 같기 때문에 다음 숫자 4.. 2025. 1. 27. [ 백준 BOJ / c++ ] 1406번 에디터 문제 https://www.acmicpc.net/problem/1406 문장 str이 주어지고, m개의 명령어를 수행한 이후의 str을 출력하는 문제이다. 또한, 문제 마지막 줄에 시작시 명령어의 커서는 맨 뒤에 위치한다고 한다.접근 방식처음에는 string의 substr을 사용해 문장을 잘라 붙이는 방식으로 진행하였다. 하지만 문장의 크기와 명령어 개수의제한이 커 시간 초과가 발생하였다.#include #include #include #include using namespace std;int main(){ /* 문자열 길이가 s 일때, 커서의 길이는 s+1로 설정 L : 커서 왼쪽 D : 커서 오른쪽 B : 0 ~ 커서위치 substr, 커서 위치 + 1 ~ s+1 까지 substr 이후 뒤에 .. 2025. 1. 23. 이전 1 2 3 다음 반응형
