선택은 나의 것

문제 BOJ 1520 : https://www.acmicpc.net/problem/1520 1520번: 내리막 길 첫째 줄에는 지도의 세로의 크기 M과 가로의 크기 N이 빈칸을 사이에 두고 주어진다. 이어 다음 M개 줄에 걸쳐 한 줄에 N개씩 위에서부터 차례로 각 지점의 높이가 빈 칸을 사이에 두고 주어진다. www.acmicpc.net 접근 내리막 길로만 갔을 때 도착지까지 갈 수 있는 경로의 갯수를 구하는 문제이다. 이는 DFS로만 풀면 시간 초과가 나기 때문에 DP + DFS를 이용하여 문제를 해결하였다. 코드 #include using namespace std; int m, n, map[505][505], visit[505][505], dx[] = {-1, 1, 0, 0}, dy[] = {0, 0..

문제 BOJ 1865 : https://www.acmicpc.net/problem/1865 1865번: 웜홀 첫 번째 줄에는 테스트케이스의 개수 TC(1 ≤ TC ≤ 5)가 주어진다. 그리고 두 번째 줄부터 TC개의 테스트케이스가 차례로 주어지는데 각 테스트케이스의 첫 번째 줄에는 지점의 수 N(1 ≤ N ≤ 500), www.acmicpc.net 접근 문제에서 웜홀은 결국 음의 값을 가지는 간선이기 때문에 벨만-포드(Bellman-Ford)알고리즘을 사용하여 문제를 해결하였다. 코드 #include #include #define endl "\n" #define MAX 30000000 using namespace std; struct eg { int s, e, t; }; int n, m, w; bool ..

문제 BOJ 2671 : https://www.acmicpc.net/problem/2671 2671번: 잠수함식별 입력에 들어있는 스트링을 읽고, 이것이 잠수함의 엔진소리를 나타내는 스트링인지 아니면 그냥 물속의 잡음인지를 판정한 후, 잠수함의 엔진 소리에 해당하는 스트링이면 "SUBMARINE"을 출력하고 www.acmicpc.net 접근 정규 표현식을 이용하여 문제를 해결하였다. 코드 #include #include using namespace std; int main() { string str; cin >> str; if (regex_match(str, regex("(100+1+|01)+"))) cout

문제 BOJ number : https://www.acmicpc.net/problem/1867 1867번: 돌멩이 제거 첫째 줄에 n과 k가 주어진다. (1 ≤ n ≤ 500, 1 ≤ k ≤ 10,000) 이후 k개의 줄에는 돌멩이의 위치가 한 줄에 하나씩 주어진다. 줄마다 첫 번째 숫자는 행 번호, 두 번째 숫자는 열 번호를 나타낸다. www.acmicpc.net 접근 이분 매칭(Bipartite Matching)을 이용하여 문제를 해결하였다. 코드 #include #include using namespace std; int n, k, ans = 0, visit[510], matchNum[510] = {0}; vector graph[510]; int dfs(int n){ for (int i : grap..

문제 BOJ 11375 : https://www.acmicpc.net/problem/11375 11375번: 열혈강호 강호네 회사에는 직원이 N명이 있고, 해야할 일이 M개가 있다. 직원은 1번부터 N번까지 번호가 매겨져 있고, 일은 1번부터 M번까지 번호가 매겨져 있다. 각 직원은 한 개의 일만 할 수 있고, 각각 www.acmicpc.net 접근 이분 매칭(Bipartite Matching)을 이용하여 문제를 해결하였다. 코드 #include #include using namespace std; int n, m, ans = 0, visit[1010], matchNum[1010] = {0}; vector graph[1010]; int dfs(int num) { for (int i : graph[num]..

문제 SWEA 2001 : 파리 퇴치 SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 접근 이 문제의 제한 조건에서 N의 값은 최대 15이기 때문에 무식한 방법으로 풀어도 무리 없이 pass가 가능하다. 쉬운 문제는 정석 풀이가 바로 떠오르지 않는다면 그냥 쉽게 가도록 하자. 코테는 시간 싸움이기 때문이다. 코드 #include #define endl "\n" using namespace std; int main() { int test; cin >> test; for (int t = 1; t > n >> m; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++)..