혼종 꼬지마루

간만에 원큐에 푼 문제라 기분이 너무 좋다... 그냥 재귀로 싹다 돌려줘도 되는 문제 물론 전체 포지션을 다 고려한다고 했을 경우에는 O(11^11)이라 밥먹고 오면 풀릴 시간이지만 문제 조건이 '한명당 적합한 포지션은 최대 5개'라는 조건이 붙어 있어서 O(5^11) 까지 줄어드는 문제 1234567891011121314151617181920212223242526272829303132333435363738394041#include #define SIZE 13using namespace std; int S[SIZE][SIZE];bool check[SIZE];int C, dab; void dfs(int d, int sum){ if (d == 11) { dab = dab > sum ? dab : sum; r..

dp를 처음 시작하면서 이 문제를 꼭 풀어보면 좋다고 생각하는 문제 dfs로 검사하며 return하는 과정에서 메모이제이션을 해주는 문제로 필수문제라고 생각 1. 맵정보를 입력받으며 dp를 -1로 초기화 2. dfs로 내리막길을 찾으며 탐색 그 위치에서의 dp는 방문한 것을 체크하기 위해 0으로 만든다. 3. 도착점에 도착하면 1을 반환한다. 4. 만약 방문한 점이고, dp가 -1이 아니라면 그 지점의 값을 반환한다. 123456789101112131415161718192021222324252627282930313233343536#include #define MX 503using namespace std; int map[MX][MX], dp[MX][MX];int dx[] = { 0, 0, -1, 1 };..

문제를 잘못 이해해서 한번 틀린 문제... 무작위가 아닌, '한줄로 이어 붙였을 때 사전 순서'라는 점에 초점을 맞추면 그다음 부터는 쉬워진다 입력을 받으며 x인 부분은 구조체 배열로 그 위치를 담아주고, A~L인 부분은 check해준다. 그다음 부터는 한 위치씩, 모든 경우의 수를 넣어주고 끝까지 넣고 난 후 조건에 맞으면 flag를 달아주고 출력하면 끝 조건을 검사하는 부분에서 따로 머리써서 단순화 시키기 보다는 그냥 무식하게 인덱스로 다 찾아서 더해줬다...ㅎ 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556#include #define MX 60using name..