asdsa112 님의 블로그

1. 알약이 최대 30개인데 반으로 쪼개 먹을 수도 있으니 최대 60번. 그러면 먹냐 안먹냐니까 최대 경우의 수가 2^60까지 될 수 있음. 2. 가능한 문자열의 경우의 수기에 경우의 수 덧셈으로 진행하면 될 것 같음. 1. 2^60은 말도 안되지만, 경우의 수 덧셈이라면 얘기가 다름. 2. 재귀로 경우의 수를 돌면서 메모제이션을 진행하면 충분히 가능할 수 있음. 3. 알약 한 조각을 꺼내면 반 조각 갯수를 올리고, 만약 반 조각을 먹는다면 한 조각 갯수를 안 내리면 됨. #include using namespace std;int n;long long dp[40][40];long long go (int day, int half){ if (day 0) { if (half 0) ..

1. 30번 이동 가능. 나무는 1번 나무, 2번 나무 존재. 그러면 경우의수가 최대 2^30임. (1번 나무 혹은 2번 나무를 30번 이동 가능하니까). 2. 그럼 무식한 완전탐색으로는 불가능. 지나왔던 길을 저장하는 방법을 택해서 복잡도를 줄여봐야 함. 1. 현재 위치에서 받을 수 있는 자두 경우의 수, 다음 위치에서 받을 수 있는 자두 경우의 수를 재귀 때 더해주는 것이 포인트임. 2. DP는 재귀 때 경우의 수를 더해주면서, 재귀 탈출 루프에서는 0의 경우의 수를 던지는 게 포인트 인 것 같음. #include using namespace std;int t, w;int tree[1004];int dp[3][31][1004]; // 현재 위치 , 남은 이동 횟수, Timeint go(int cu..

1. 만약 완탐으로 해보겠다. 라고 생각한다면,4방향, 50*50보드면 4^2500 경우의 수임. 2. 그럼 방문처리해서 DFS 식으로 혹은 DP로 간다면 O(M*N)에 상수 4방향 해서 약 10000번 정도. 1. 방문 처리 된 곳을 방문했다면 사이클 이므로 -1을 출력하고 exit 하는 것도 방법. 2. DP는 DFS가 탐색하고 있는 그 경로 자체의 함수 호출스택이 경우의 수를 탐색하고 있는 거라고 생각해보면 됨. 3. 그렇게 생각하면 맵을 벗어났을 때는 게임이 끝난 것 이므로 경우의 수 0을 반환. go 재귀로 들어갈 때는 경우의 수 1개가 추가되는 거임. #include using namespace std;int n, m;int dp[50][50];char board[50][50];int v..

1. 방법의 수를 모두 더해라 -> 경우의 수 문제겠다. 라고 생각해봄. 2. 파이프가 두 개의 좌표를 물고 있고 대각선일 때는 3개의 좌표를 벽이 있는지 체크함. 1. 파이프를 옮기는 로직을 생각해내기가 진짜 어려웠음. 2. 파이프의 앞선 좌표는 생각할 필요 없음. 이동되는 끝 좌표만 생각하면 됨. 3. 그렇게 되면 끝 좌표 따라 벽 체크, 좌표 이동만 해주면 됨. 4. 그러면 DFS도 가능함. 결국 DFS도 "모든 경로"를 탐색하면서 목적지까지 도달하게 끔 순회하는 것이므로 모든 경우의 수를 탐색해볼 수 있음. (도시의 수가 적어서 가능한 방법이기도 함) 5. DP의 핵심은 부분최적해를 발견하고 그것을 더해나가거나 어떻게 캐싱하느냐의 문제임. 6. 여기서 DP의 부분최적해는 해당 위치에서 방향에 따..

1. 만약 도시를 a -> b -> c -> d -> a 방향으로 방문한다고 했을 때, a->b 의 최소, b->c의 최소 이렇게 부분최적해를 쌓아나가는 문제임. 2. 왔던 그 경로를 캐싱으로 저장해놓으면 됨. 3. 만약 도시를 방문하는 순서가 중요하다면 N이 최대 16이므로 16! = 20조가 됨. (16개 방문 * 15개 방문 * 14개 방문 ...) 4. 순서가 중요하지 않으니 16개의 도시를 집합으로 관리할 수 있게 됨. -> 비트마스킹으로 가능함. 1. dp의 배열 구조를 [방문한 지점][지금까지 방문한 비트상태] 로 관리함. 2. 최소값을 구하는 것 이므로 항상 inf로 설정해놓아야 함. (INT_MAX는 프로그래머스에서 사용 불가)#include using namespace std;#def..