개발개굴🐸

[문제] https://www.acmicpc.net/problem/14943 14943번: 벼룩 시장 벼룩시장에서 사람들이 벼룩을 사고 판다. 놀랍게도 각 사람들이 사려고 하는 벼룩의 합과 파는 벼룩의 합은 같다. 벼룩을 사거나 파는 사람들은 서로 일렬로 길게 서 있으며, 인접한 가게 사이 www.acmicpc.net [풀이] +값은 판매 배열(sale[]), -값은 구매 배열(buy[])에 각각 저장한 후 투포인터를 활용하여 문제를 해결하였습니다. 1. info[]에 담겨있는 벼룩 시장 정보들을 sale과 buy에 [금액, index] 형태로 저장합니다. 2. 판매 정보와 구매 정보로 투포인터를 진행합니다. buy의 위치를 저장한 left 변수와, sale의 위치를 저장한 right 변수를 각각 0으로..

[문제] https://www.acmicpc.net/problem/24513 24513번: 좀비 바이러스 여기 $N$ x $M$ 격자 모양의 마을이 있다. 어느 날 세상에 좀비 바이러스가 창궐하여 바이러스가 빠르게 퍼져나가버린다. 바이러스에 대해 조사한 결과 세 종류의 바이러스가 존재했으며 각각 $1$ www.acmicpc.net [풀이] BFS를 통해 바이러스를 퍼트립니다. 초기 세팅 village : 마을 정보 저장 virus: [x좌표, y좌표, 바이러스 타입] 형태로 바이러스 정보 저장 checkOut(x, y) : 마을을 벗어난 위치면 true, 마을 안에 있다면 false를 반환 풀이 과정 bfs를 통해 갱신되는 바이러스 정보를 virus에 저장하며 모두 검사합니다. 이때 주의할 점은 동시간대..

[문제] https://www.acmicpc.net/problem/3980 3980번: 선발 명단 각각의 테스트 케이스에 대해서, 모든 포지션의 선수를 채웠을 때, 능력치의 합의 최댓값을 한 줄에 하나씩 출력한다. 항상 하나 이상의 올바른 라인업을 만들 수 있다. www.acmicpc.net [풀이] 단순히 DFS를 통해 선수 배치가 가능한 모든 조합을 완전 탐색하는 문제였습니다. 1. position 배열에 각 선수들의 가능한 포지션과 능력을 저장합니다. position의 i번째 배열에 [가능한 포지션, 능력] 형태로 push합니다. 따라서 예제의 position 정보를 모두 저장하면 다음과 같습니다. [ [ [ 0, 100 ] ], [ [ 1, 80 ], [ 2, 70 ], [ 3, 70 ], [ 4..

[문제] https://www.acmicpc.net/problem/1522 1522번: 문자열 교환 a와 b로만 이루어진 문자열이 주어질 때, a를 모두 연속으로 만들기 위해서 필요한 교환의 회수를 최소로 하는 프로그램을 작성하시오. 이 문자열은 원형이기 때문에, 처음과 끝은 서로 인접해 www.acmicpc.net [풀이] a를 모두 연속적으로 만들기 위해선 우선 문자열의 총 a 개수를 구해야 합니다. a의 총 문자 개수(len)의 구간으로 슬라이딩 윈도우를 통해 구간에 포함된 a의 개수를 구합니다. (총 a의 개수(len)) - (가장 많은 개수를 포함한 구간의 a개 수)를 통해 최소 이동 횟수를 구합니다. 예를 들어 문자열이 "ababa"라고 한다면 풀이 과정은 다음과 같습니다. len = 3 이므..

[문제] https://www.acmicpc.net/problem/20437 20437번: 문자열 게임 2 첫 번째 문자열에서 3번에서 구한 문자열은 aqua, 4번에서 구한 문자열은 raquator이다. 두 번째 문자열에서는 어떤 문자가 5개 포함된 문자열을 찾을 수 없으므로 -1을 출력한다. www.acmicpc.net [풀이] 어떤 문자를 a라고 한다면 정확히 K개를 포함하며, 첫 번째와 마지막 글자가 모두 a인 문자열의 길이를 구해야 합니다. 따라서 for문으로 문자열W을 순회하며 K개 이상 포함된 문자를 찾아야합니다. 1. Map을 활용하여 key = 문자 , value = [문자의 개수, index1, index2, ... ] 의 형태로 저장해 주었습니다. 2. 완성된 Map을 순회하며 val..

[문제] [풀이] 수빈이가 동생을 찾아서 이동할 수 있는 방법은 2가지가 있습니다. 1초 동안 -1 칸 or +1 칸 이동 0초 동안 순간이동하여 X2칸 이동 따라서 규칙적으로 이동하는 것을 보고 DP를 활용하여 풀이하였습니다. 1. 수빈이 위치 N보다 작은 칸으로는 순간이동이 불가능해서 항상 1초가 걸려 -1칸씩 이동해야합니다. N보다 작은 위치는 0에서 1초씩 시간을 증가시켜 각 dp 배열의 위치 인덱스에 시간을 저장 2. 수빈이 위치 N을 0초로 시작해서 N보다 큰 칸으로 이동하는 경우는 걷기와 순간이동 2가지가 있습니다. 따라서 현재 위치를 X라고 했을때, X위치로 이동할 수 있는 경우는 2가지가 있습니다. X-1에서 +1칸 걸어온 경우 : 1초의 시간이 걸림 => dp[X-1] + 1 X/2 칸..

[문제] https://www.acmicpc.net/problem/2457 2457번: 공주님의 정원 첫째 줄에는 꽃들의 총 개수 N (1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 각 꽃이 피는 날짜와 지는 날짜가 주어진다. 하나의 날짜는 월과 일을 나타내는 두 숫자로 표현된다. 예를 들어서, www.acmicpc.net [풀이] find()를 통해 가장 적게 꽃을 피울 수 있는 조합을 구해주었는데, find()는 아래와 같은 작업을 반복합니다. 아직 방문하지 않은(피우지 않은) 꽃 중에서 현재 조회중인 시작 날짜와 같거나 이전에 피어서 가장 늦게 지는 꽃을 찾아서 해당 꽃의 index를 저장 만약 꽃을 찾지 못했다면 조건을 만족하지 못하여 0을 출력하고 종료 만약 조회된 index의 ..

[문제] https://www.acmicpc.net/problem/1806 1806번: 부분합 첫째 줄에 N (10 ≤ N min ..