문제 링크 1744번: 수 묶기 풀이 그리디 문제 아이디어는 양수는 양수끼리 절댓값이 큰 것끼리 묶고, 음수는 음수끼리 절댓값이 큰 것끼리 묶는다. 값을 입력받으며 양수이면 plus 벡터에 넣고, 음수면 minus 벡터에 넣는다. plus는 내림차순 정렬, minus는 오름차순 정렬한다. greedy함수를 통해 각 벡터의 최댓값을 구해 더해준다. 2번 과정을 통해 각 벡터는 절댓값이 큰 순서대로 내림차순 정렬 되어 있을텐데, 처음부터 묶어주거나 묶지 않거나를 선택해준다. 선택은 현재 숫자와 다음 숫자의 곱이 합보다 클 경우에 묶어준다. 묶어줄 경우 인덱스는 +2를 해줘야 중복해서 묶지 않게 된다. 묶지 않을 경우 인덱스를 +1 해줘서 그 다음 숫자와 묶일 수 있는지 확인하도록 한다. 그렇게 구한 양수와 ..
문제 링크 5052번: 전화번호 목록 풀이 문자열 문제. 처음에는 완탐으로 했는데 시간초과가 나길래.. 찾아보았다. 정렬하는 것까진 맞았는데, 정렬을 하게 되면 바로 뒤에꺼만 확인하면 된다. 하하 문자열을 입력받고 정렬한다. 현재 문자열을 기준으로 다음 문자열을 substr로 잘라서 같은지 확인한다. 같으면 NO, 전체 확인이 끝나도 flag가 true라면 YES를 출력한다. 코드 #include #include #include #include using namespace std; int main() { ios_base::sync_with_stdio(0); cin.tie(0); int t; cin >> t; for (int i = 0; i > n; vector ..
문제 링크 1339번: 단어 수학 풀이 그리디를 사용하는 문제 처음엔 그냥 순서대로 점수 넣으려다 ACA BBD 같은 반례가 생각나서 우선순위? 느낌으로 변경함 문제를 입력받으며 가장 긴 문자열의 길이를 구해준다. maxLen 각 단어마다 알파벳의 우선순위를 구해주는데, ABC라는 단어가 있음면 A=100, B=10, C=1이 되게 구해준다. 그러면 각 알파벳마다 우선순위가 구해지는데, map으로 되어있기 때문에 vector로 바꿔주어 value기준 내림차순 정렬을 해준다. 우선순위가 높은 알파벳부터 9를 배정해주고 값을 하나씩 줄이며 숫자를 대응해준다. 다시 단어를 돌면서 대응한 숫자를 넣고 answer에 더해준다. 코드 #include #include #include #include #include ..
문제 링크 11057번: 오르막 수 풀이 DP로 푸는 문제 1자리 수일 때는 0~9까지 10개 2자리 수일 때는 00~09, 11~19 ~ 99해서 55개이다. 규칙은 n길이의 맨 첫번째 숫자가 만약 5라고 한다면 n-1길이의 숫자에서 55~99까지의 개수가 5로 시작하는 오르막 수의 개수일 것이다. 3 길이의 5로 시작하는 오르막 수를 구한다면, 555~559, 566~569, ..., 588~589, 599가 될 것이다. 해당 범위로 자른 이유는 n-1길이에서 55~59의 개수, 66~69의 개수 .. 를 구했을 것이기 때문이다. 점화식은 arr[n][i] = arr[n-1][i] + arr[n][j+1] (누적합으로 구해줄 것임) 코드 #include #include #define mod 10007..
문제 링크 9465번: 스티커 풀이 DP를 이용하는 문제 예시가 문제와 같이 다음 표라고 생각해보면 50 10 100 20 40 30 50 70 10 60 다음과 같이 생각할 수 있다. 50 10 + 30 100 + max(100, 30) = 200 20 + max(120, 100) = 140 40 + max(210, 120) = 250 30 50 + 50 70 + max(40, 50) = 120 10 + max(200, 40) = 210 60 + max(140, 200) = 260 정리하면, 해당 칸을 뜯는다고 가정할 때, 바로 대각선을 뜯을 것이냐 아니면 그 전 대각선을 뜯을 것이냐만 생각하면 된다. 점화식은 dp[0][j] = dp[0][j] + max(dp[1][j-1], dp[1][j-2]) 코..
문제 링크 11052번: 카드 구매하기 풀이 DP를 이용하는 문제 점화식을 구한다. n이 4라고 하면 4개짜리 하나 사는 경우와 `,2,3개짜리를 섞어서 사는 여러 경우가 있을 것이다. dp의 i번째 인덱스는 i개를 살 때 최댓값을 지불하는 경우가 저장되어 있을 텐데, 이를 이용해 1개짜리 사는 최댓값과 3개짜리 사는 최댓값을 더한 경우, 2개짜리 살 때 최댓값을 두 번 지불하는 경우, 그냥 4개짜리 사는 경우들에서 최댓값을 구해준다. 정리하면 점화식은, dp[n] = max(dp[1]+dp[n-1], dp[2]+dp[n-2], ... , dp[n/2]+dp[n-n/2], dp[n](입력하면서 그냥 여기에 넣어줄거임))이 될 것이다. 점화식을 이용해 코드를 짜는데, 같은 경우를 두 번 계산하지 않기 위해..
문제 링크 배달 풀이 다익스트라로 푸는 문제인데 최소신장트리로 헷갈려서 약간 돌아갔다. 입력받은 road를 이용해 인접리스트를 만들어준다. 거리가 갱신될 dist는 최댓값으로 초기화해준다. 우선순위 큐로 최단 거리를 갱신해준다. 거리 순으로 정렬 되도록 pair를 {cost, end} 형태로 만들어준다. 그리고 오름차순 정렬한다. dist[next]>dist[cur]+nextCost라면 거리가 갱신된다는 것이므로 갱신해준 뒤 pq에 push한다. 그렇게 만들어진 dist를 돌면서 k보다 작거나 같다면 1 더해준다. 코드 #include #include #include #define INF 20000001 using namespace std; int solution(int N, vector road, in..
문제 링크 미로 탈출 풀이 BFS를 이용하는 문제 미로를 만들면서 출발 지점인 stt와 도착 지점인 end를 만들어준다. BFS를 돌리는데 시간이 갱신될 time을 3차원 배열로 만들어준다. 원래 2차원 배열의 BFS는 방문한 지점을 다시 방문하지 않는데, 이 문제는 레버를 누르고 도착 지점으로 가야하기 때문에 왔던 길을 다시 방문할 수도 있다. 구조체 Cell을 정의한다. 위치가 담길 y와 x, 레버가 당겨졌었는지 확인할 flag로 구성되어 있다. 도착지점부터 q에 넣고 상하좌우를 탐색한다. 범위 밖이거나 벽이거나 방문 했었다면 continue, 레버라면 해당 지점에서 차원이 옮겨지게 된다. time을 갱신하고 q에 새로운 위치를 넣어준다. time[end.first][end.second][1]을 re..
문제 링크 아이템 줍기 풀이 BFS문제인데, 좌표를 두 배 확대하는 아이디어로 풀 수 있는 문제 2배하게 되면 각 영역의 점과 점을 잇는 선을 따로 구할 수 있어 겹치는 문제를 해결할 수 있다. 각 좌표는 50이하로 들어오므로 배열은 원래 51 사이즈로 만들어야하는데, 두 배이기 때문에 102 크기로 만든다. 사각형을 돌면서 각 좌표는 두 배해주고 1로 영역을 만들어준다. 좌표의 시작+1부터 끝-1까지는 안쪽이기 때문에 0으로 만든다. 외곽선을 BFS로 탐색하면서 거리를 구해주고, 답은 /2해줘야 나온다. 코드 #include #include #include #include using namespace std; int dy[4] = {-1,0,1,0}; int dx[4] = {0,1,0,-1}; int ..
문제 링크 14940번: 쉬운 최단거리 풀이 BFS를 이용하는 문제. 반례를 잘못 처리해서 틀렸었음 3 3 2 0 0 0 0 1 0 1 1 입력을 받으며 목표지점일 경우(2일 경우)에는 dest에 넣어준다. BFS를 시작한다. 각 거리가 갱신될 벡터 dist는 -1로 초기화한다. 보통 난 0으로 초기화해주는데, 여기서 갈 수 있는 길인데 못 가는 경우를 처리하기 위해 -1로 처리한다. 상하좌우를 돌면서 범위 밖이거나 0이라면 continue한다. 각 거리를 갱신해준 뒤 q에 push한다. dist를 출력하는데, 반례와 같이 원래 못 가는 곳은 0으로 처리해야 하는데, -1로 출력될 수 있어 여기서 처리해준다. arr[i][j]가 0인데 dist[i][j]가 0이 아니라면 0으로 만들어준 뒤 출력한다. 코..
