본문 바로가기

코딩/알고리즘

 (67)
SW expert academy 1824 혁진이의 프로그램 검증 기본적인 풀이는 DFS이다. DP[i][j][memory][direct]는 "i, j의 위치에서 memory의 값을 메모리에 저장해놨을 때, direct로 프로그램이 진행되고 있는 상황에서의 프로그램이 끝날 수 있는 지의 여부"이다.그 결과값이 1이면 끝날 수 있고, 2이면 끝날 수 없음을 의미한다. 혁진이의 프로그램이 무한루프가 돈다는 것은, 같은 memory와 direct의 상황에서 같은 i,j를 방문했다는 것으로 체크하면 된다. #define _CRT_SECURE_NO_WARNINGS #include #include #include #include #include #include #include #include #include #include #include #include #include #inc..
SW expert academy 1238 Contact #define _CRT_SECURE_NO_WARNINGS #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; int len, start; int main() { for (int tc = 1; tc > from; cin >> to; adj[from].insert(to); } queue next; bool isVisit[101]; for (int i = 0; i < 101; i++) { isVisit[i] = false; } //isVisit[start] = true; next.push(start); next.pus..
SW expert academy 1227 미로2 #define _CRT_SECURE_NO_WARNINGS #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; int len, start; int moves[4][2] = { {-1,0}, {0, -1}, {1, 0}, {0, 1} }; int arr[100][100]; set adj[100][100]; int main() { for (int tc = 1; tc > testcasenum; int starti, startj, endi, endj; for (int i = 0; i < 100; i++) { string ..
SW expert academy 1251 하나로 #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; int N; double E; long long node[1000][2]; //i, j 저장 long long adj[1000][1000]; // i j의 비용 int main() { int tcm; scanf("%d", &tcm); for (int tc = 1; tc
백준 17069 파이프 옮기기2, 17070 파이프 옮기기1 #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; typedef long long lld; int N; int arr[32][32]; lld memo[32][32][3]; lld dp(int i, int j, int mode) { if (i 31 || j 31) { return 0; } lld& m = memo[i][j][mode]; if (m != -1) return m; if (i == 0 && j == 1 && mode == 0) { m = 1; return m; }..
백준 1315 RPG 백준 1315 RPG C++17의 auto && [a, b, c] = tuple t; 구문을 적극 활용 solve(i,j)는 str가 i, int가 j일 때, 이 이후로 내가 깰 수 있는 최대갯수의 퀘스트 이다. solve(i,j)에서 현재 스텟에서 깰 수 있는 퀘스트 갯수를 새고그 퀘스트를 깻다고 표시한 뒤깰 수 있는 퀘스트들의 포인트들의 합으로 스탯을 배분하여solve()를 재귀로 호출한다. 이때, 재귀로 들어오기 전에 깻던 퀘스트들은 또다시 깨면 안되기 때문에 깨지 않은 퀘스트만 깨고, 다시 위에서 설명한 것처럼 퀘스트 포인트 합으로 스탯 배분 후 다시 재귀 호출을 한다 그리고 재귀호출이 모두 끝나서 리턴하여 본래 함수로 되돌아 오면스탯을 배분한 수많은 상황중에서 가장 많이 깰 수 있는 퀘스트의 갯..
백준 11062 카드게임 백준 11062 카드게임 solve(i,j)는 i에서 j까지의 카드(i와j는 인덱스)만 남았을 때,""지금 상황에서"" = end) { if ((N - (start + end)) % 2) return ret = card[start]; else return ret = 0; } if ((N - (start + end)) % 2){ ret = max((solve(start + 1, end) + card[start]), (solve(start, end - 1) + card[end])); } else { ret = min((solve(start + 1, end)), (solve(start, end - 1))); } return ret; } int main() { scanf("%d", &testcase); whil..
백준 2618 경찰차 boj 2618 DP[i][j] = 1번 경찰차가 i위치, 2번 경찰차가 j위치에 있을때의 최소 비용(max(i,j)의 사건까지 처리한 상황) dist(a, b)는 a번 사건 위치와 b번 사건 위치사이의 거리 (i > j 일때,)DP[i][j] = DP[i-1][j] + dist(i, i-1) (if abs(i-j) != 1) DP[k][j] = dist(k, i) (if(abs(i-j) == 1), k는 0~i-2까지 DP[i][j]는 max(i,j)번 사건까지 처리한 상황이기 때문에 DP[i][j]를 계산하기 위한 식들은 인덱스의 최대값이 max(i,j)보다 1 작아야 하므로 위의 식이 성립한다 #define _CRT_SECURE_NO_WARNINGS #include #include #include ..

티스토리툴바