BFS bfs로 풀었음 플로이드 와샬 풀이가 바로 떠올라서 최대한 bfs로 풀려고 노력했다. 즉 어느 하나의 노드를 기준으로 탐색하게 되면, 해당 노드로부터 다른 노드까지의 depth를 bfs로 탐색해가며 구할 수 있다. 시작이되는 어떤 노드를 queue(이하 q로 부름) 에 삽입한다. q를 pop해 그 노드와 인접한 (adj, copy 배열이 1), 방문하지 않은 노드를 그 다음으로 선정한다. 이때 depth를 1씩 증가한다. 이는 시작노드로부터의 depth가 현재 pop한 x(현재 노드)까지의 depth보다 1이 증가함을 의미한다. 다른 말로, 0-1-2 순으로 노드가 있으면, 0-2까지의 depth는 0-1까지의 depth + 1이다. 그렇게 해서 q가 비었다면, 즉 모든 노드를 탐색했다면 저장된 ..

하.. https://www.acmicpc.net/problem/1786 1786번: 찾기 첫째 줄에, T 중간에 P가 몇 번 나타나는지를 나타내는 음이 아닌 정수를 출력한다. 둘째 줄에는 P가 나타나는 위치를 차례대로 공백으로 구분해 출력한다. 예컨대, T의 i～i+m-1번 문자와 P의 1～m www.acmicpc.net 글 읽기 - 40% 쯤에서 틀립니다 문제가 뭔지 도저히 모르겠어요... 댓글을 작성하려면 로그인해야 합니다. www.acmicpc.net #include #include #include #include #include using namespace std; void kmp(string t, string p, vector &box) { int ans = 0; int i = 0, j = 0..

https://www.acmicpc.net/problem/1913 1913번: 달팽이 N개의 줄에 걸쳐 표를 출력한다. 각 줄에 N개의 자연수를 한 칸씩 띄어서 출력하면 되며, 자릿수를 맞출 필요가 없다. N+1번째 줄에는 입력받은 자연수의 좌표를 나타내는 두 정수를 한 칸 띄어서 www.acmicpc.net 정-직하게 2차원 배열의 가운데부터 1씩 증가하며 달팽이 모양(상, 우, 하, 좌) 순으로 2차원 배열을 탐색했다. 내가 이미 채운 곳이라면 (이미 어떤 cnt라는 정수가 채워져 0이 아니라면) 왔던 방향을 한번 더 가면된다. 이는 곧 현재의 방향을 나타내는 iterator i를 2 감소하면 된다. 1을 감소하면 되는게 맞지만, 현재 내가 수행한 반복문의 끝에서 1이 증가하므로 그것까지 고려해 2를..

https://www.acmicpc.net/problem/2468 2468번: 안전 영역 재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는 www.acmicpc.net q.pop()을 빼먹어서 queue 길이가 자꾸만 증가하는 이유를 찾으려 디버깅을 계속했다... ㅠㅠ 76%에서 틀렸었는데, 아무 칸도 물에 잠기지 않을 수 있다는 조건을 빼먹었기 때문이다. 유사 문제 떨어진 영역(뭉탱이)의 개수를 구하는 방법을 모르겠다면 아래 문제와 해답을 참고하면 도움될 것이다. 2021.09.26 - [PS/백준] - 백준 4963번 (C++) 섬의 개수 백준 4963번 (C++)..

https://www.acmicpc.net/problem/14442 14442번: 벽 부수고 이동하기 2 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 1,000), K(1 ≤ K ≤ 10)이 주어진다. 다음 N개의 줄에 M개의 숫자로 맵이 주어진다. (1, 1)과 (N, M)은 항상 0이라고 가정하자. www.acmicpc.net 아이디어 가려는 칸이 0이면 진행한 칸 수인 cnt+1하고 queue에 넣고, 1이라면 cnt+1, block+1해서 push 했다. 틀림 #include #include #include using namespace std; const int MAX = 1000; int N,M,K; char arr[MAX][MAX]; int dx[] = {-1, 0, 1, 0}..

https://www.acmicpc.net/problem/2644 2644번: 촌수계산 사람들은 1, 2, 3, …, n (1 ≤ n ≤ 100)의 연속된 번호로 각각 표시된다. 입력 파일의 첫째 줄에는 전체 사람의 수 n이 주어지고, 둘째 줄에는 촌수를 계산해야 하는 서로 다른 두 사람의 번호가 주어 www.acmicpc.net bfs로 queue에 현재 노드 번호(cur or i)와, 현재 그 노드가 가진 촌수(cnt)를 pair형으로 기록하며 넣어주었다. 현재 노드와 다음 노드가 인접하다면 (arr[cur][i] 가 1이라면) queue에 cnt+1하여 push한다. 10분만에 아래 틀린 코드를 짜놓고 잔뜩 뿌듯해하며 냈는데 33%에서 틀려서 부랴부랴 고쳤다. 우선 양방향 그래프로 구현되기에 방문체..

https://www.acmicpc.net/problem/23559 23559번: 밥 제주대 학생회관 식당에는 두 개의 메뉴가 있다. 코너 A로 가면 5,000원짜리 메뉴를 먹을 수 있고, 코너 B로 가면 1,000원짜리 메뉴를 먹을 수 있다. 준원이는 대면 수업이 시작되는 바람에 이제 남 www.acmicpc.net 틀린 코드 #include #include #include #include using namespace std; int n, x; vector v; bool cmp(pair p1, pair p2) { double a = (double)(p1.first) / (double)(p1.second); double b = (double)(p2.first) / (double)(p2.second); i..

아이디어 재귀를 연습하기에 좋은 문제였다. 재귀의 base case는 길이가 1일때이다. (길이가 1일때는 팰린드롬이다.) 길이가 2 이상인 경우는, 문자열을 반으로 나눈다. 길이가 짝수인 경우, 반으로 그대로 나누고, 홀수인 경우는 가운데 문자를 기준으로 반으로 나눈다. 이때 반으로 나눈 문자열 다르다면 바로 "아카라카"의 조건에서 탈락이다. 반으로 나눈 그 문자열을 다시 재귀함수의 인자로 넣음으로서 해당 문자열 또한 "아카라카"인지 검사한다. 반으로 나눈 기준 앞 뒤의 문자열이 모두 아카라카라면 합친 문자열 또한 아카라카이다. https://www.acmicpc.net/problem/23304 23304번: 아카라카 주어진 문자열 $S$가 아카라카 팰린드롬이라면, AKARAKA를 출력한다. 만약 그렇..

n의 입력이 작기 때문에 브루트포스(완전 탐색)으로 풀어도 무리가 없다. 자신보다 키, 몸무게 둘 다 큰 경우 cnt++한다. https://www.acmicpc.net/problem/7568 7568번: 덩치 우리는 사람의 덩치를 키와 몸무게, 이 두 개의 값으로 표현하여 그 등수를 매겨보려고 한다. 어떤 사람의 몸무게가 x kg이고 키가 y cm라면 이 사람의 덩치는 (x, y)로 표시된다. 두 사람 A 와 B의 덩 www.acmicpc.net #include #include #include using namespace std; vector v; int main(void){ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n,x, ans = 0..

아이디어 처음엔 삼각형의 위에서부터 1층, ..., k층, ..., n층으로 생각하고 k층까지의 최적의 경로가 n층까지의 최적의 경로에 포함될 것이라 생각할 수도 있다. 그러나 예시로 주어진 테스트케이스가 그 반례이다. 따라서 최적의 경로는, 2차원배열의 각 인덱스에 해당하는 dp[i][j]에 저장되어있다. 그러므로 dp[i][j]에 도달하는 optimal한 경로와 dp[i][j+1]에 도달하는 경로가 다를 것이다. dp[i][j] = max(dp[i-1][j], dp[i-1][j-1]) + arr[i][j]; 를 사용하여 해결하면 된다. 다시 말하자면, k층까지 탐색했을 때 합이 최대가 되는 것이 최적의 경로가 아니라, k층의 l열을 오는 데에 합이 최대가 되는 경로가 최적의 경로(dp의 점화식)을 구..