https://www.acmicpc.net/problem/7490 7490번: 0 만들기 각 테스트 케이스에 대해 ASCII 순서에 따라 결과가 0이 되는 모든 수식을 출력한다. 각 테스트 케이스의 결과는 한 줄을 띄워 구분한다. www.acmicpc.net 1. Logic - 처음 시작 1은 무조건 양수로 시작한다고 이해하고 풀었다. 왜냐면 -1 -2 +3도 있지만 테케에 포함되지 않기 때문에 n = 9일 때를 생각해 보면 처음에 12가 들어오는 경우도 생기기 때문에 1을 먼저 박고 시작하지 않고 0일때를 분할하여 계산해주었다. 부분 문제 1. cnt == 0일때(처음 시작일 때) - 1을 더할지 - 12를 더할지 2. cnt == 0이 아닐때(처음 시작이 아닐때) - 한자리만 더할지 - 한자리만 뺄지..
알고리즘 풀이
https://www.acmicpc.net/problem/1987 1987번: 알파벳 세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으 www.acmicpc.net 1. Logic - 문자 하나를 지날 때 마다 체크를 해서 다음 경로에서 이전에 어떤 문자를 지나왔는지를 확인해야하기 때문에 처음에는 자료구조 중 map을 사용해서 체크했다. 경로를 체크한 후 방문 처리한 계속 남아있게 되면 다른 경로를 진입할 때 continue 처리가 되기 때문에 DFS를 빠져나오면서 map에서 키값을 false로 돌려놔준다. 방문처리 하는 법 1. 자료구조 Map을 활..
https://www.acmicpc.net/problem/2302 2302번: 극장 좌석 주어진 조건을 만족하면서 사람들이 좌석에 앉을 수 있는 방법의 가짓수를 출력한다. 방법의 가짓수는 2,000,000,000을 넘지 않는다. (2,000,000,000 n + 1) ..
https://www.acmicpc.net/problem/20303 20303번: 할로윈의 양아치 첫째 줄에 정수 $N$, $M$, $K$가 주어진다. $N$은 거리에 있는 아이들의 수, $M$은 아이들의 친구 관계 수, $K$는 울음소리가 공명하기 위한 최소 아이의 수이다. ($1 \leq N \leq 30\ 000$, $0 \leq M \leq 100\ 000$, www.acmicpc.net 1. Logic - 친구관계를 bfs를 돌면서 친구관계를 만들어준다. - Knapsack 알고리즘을 활용하여 사탕을 뺏을 수 있는 가치합의 최대값을 구해준다. 2. Code #include using namespace std; int n, m, k; vector vec[30001]; bool vis[30001];..
https://www.acmicpc.net/problem/14938 14938번: 서강그라운드 예은이는 요즘 가장 인기가 있는 게임 서강그라운드를 즐기고 있다. 서강그라운드는 여러 지역중 하나의 지역에 낙하산을 타고 낙하하여, 그 지역에 떨어져 있는 아이템들을 이용해 서바이벌을 www.acmicpc.net 1. Logic - 모든 점에서 모든 점까지의 최단 거리를 각각 구해야한다. >> 플로이드 와샬 알고리즘 플로이드 와샬 알고리즘은 3중 for문을 돌아야하기 때문에 노드의 갯수가 적을 때 사용할 수 있다. 2. Code #include using namespace std; int n, m, r; const int INF = 0x3f3f3f3f; vector dist(101, vector (101, IN..
https://www.acmicpc.net/problem/2206 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net 1. Logic - 방문처리를 하는 vis배열을 2차원으로 좌표로만 구성하는 것이 아닌 3차원으로 형성하여 벽을 뚫을 수 있는지 아니면 이전에 뚫은 적이 있는지 확인한다. 부분문제를 나눠보자면 1. 벽을 뚫을 기회가 있을 때 벽을 만난경우 2. 갈 수 있는 길이면서 방문한적 없는 경우 이렇게 2가지로 나눌 수 있다. 2. Code #include using namespac..
https://www.acmicpc.net/problem/7570 7570번: 줄 세우기 입력은 2 개의 줄로 이루어져 있다. 첫 줄에는 어린이 수를 나타내는 정수가 주어진다. 둘째 줄에는 처음에 줄서있는 어린이들의 번호가 차례대로 주어진다. 주어진 번호들 사이에는 공백이 하 www.acmicpc.net 1. Logic - 줄세우기 문제는 최장 증가 부분 수열(LIS) 를 사용해서 풀이한다. LIS로 풀이하는 이유는 이미 순서대로 서있는 가장 많은 수를 제외한 나머지의 위치를 변경해주면 되기 때문이다. 2. Code #include using namespace std; int n; vector vec; int dp[1000001]; int main() { ios_base::sync_with_stdio(f..
https://www.acmicpc.net/problem/2470 2470번: 두 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 1,000,00 www.acmicpc.net 1. Logic 음수와 양수가 섞여있기 때문에 먼저 오름차순으로 정렬을 한다. 두개의 포인터중 하나는 음수에서부터 하나은 양수에서 부터 서로 끝과 끝에서 가운데로 모이는 방식으로 투포인터를 적용한다. 2. Code #include using namespace std; const long long INF = 1e12; vector ans(2); vector vec;..
https://www.acmicpc.net/problem/2003 2003번: 수들의 합 2 첫째 줄에 N(1 ≤ N ≤ 10,000), M(1 ≤ M ≤ 300,000,000)이 주어진다. 다음 줄에는 A[1], A[2], …, A[N]이 공백으로 분리되어 주어진다. 각각의 A[x]는 30,000을 넘지 않는 자연수이다. www.acmicpc.net 1. Logic - 인덱스를 가르키는 두개의 포인터 변수(start, end)를 선언 한 뒤 원하는 수보다 sum이 작으면 다음 배열로 end를 옮기고 vec[end] 더해주고 크면 vec[start]를 빼주고 start 포인터를 하나 더해준다. 해당 문제는 투포인터를 설명하면서 똑같이 풀이해놨으니 투포인터를 잘 모른다면 다음 글을 참고하면 좋을 것 같다!..
https://www.acmicpc.net/problem/1806 1806번: 부분합 첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다. www.acmicpc.net 1. Logic - 인덱스를 가르키는 두개의 포인터 변수(start, end)를 선언 한 뒤 원하는 수보다 sum이 작으면 다음 배열로 end를 옮기고 vec[end] 더해주고 크면 vec[start]를 빼주고 start 포인터를 하나 더해준다. Testcase 하나를 예시로 들어보면 Testcase 10 4 5 1 3 5 10 7 4 9 2 2 여기서 더해서 4가 되는 연속되는 인..
