본문 바로가기

dfs4

2098 - 외판원 순회 https://www.acmicpc.net/problem/2098 2098번: 외판원 순회 첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 16) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j www.acmicpc.net 주의할 점 최대 값을 주고 돌리는 경우 방문을 해서 최대 값인지 아닌지를 알 수가 없어 무한루프가 발생한다. -1을 준 뒤 방문을 구분하자. 코드 #include #include #include #include using namespace std; typedef pair PII; int N; vector ways[16]; int dp[16][1 >N; for(.. 2023. 7. 18.
3109 - 빵집 https://www.acmicpc.net/problem/3109 3109번: 빵집 유명한 제빵사 김원웅은 빵집을 운영하고 있다. 원웅이의 빵집은 글로벌 재정 위기를 피해가지 못했고, 결국 심각한 재정 위기에 빠졌다. 원웅이는 지출을 줄이고자 여기저기 지출을 살펴보던 www.acmicpc.net 생각해보기 이동 가능 방향은 ↗➡↘로 3가지가 있다. 맨 위에서 부터 시작해서 아래로 내려가며 탐색하면 된다. 이미 이동한 곳은 통과가 가능하던 불가능하던 다시 방문할 필요가 없으므로 방문체크를 해주자. 코드 #include #include using namespace std; int R,C; int ans=0; string pipes[10001]; int my[3]={-1,0,1}; void input(){ c.. 2023. 6. 29.
9655 - 돌 게임 https://www.acmicpc.net/problem/9655 9655번: 돌 게임 상근이가 게임을 이기면 SK를, 창영이가 게임을 이기면 CY을 출력한다. www.acmicpc.net 생각해 보기 상근이와 창영이는 항상 최선의 수만을 둔다. 만약 1개를 놓던 3개를 놓던 자신이 이기는 경우가 있다면 그 수만 둘 것이다. 이미 해봤던 경우를 메모이제이션으로 지워주자. 코드 더보기 #include using namespace std; int N; int dp[1001][2]; int dfs(int cnt, int who){ if(dp[cnt][who]) return dp[cnt][who]; int wflag = who?1:-1; int fflag = who?-1:1; if(cnt==N) return f.. 2023. 2. 23.
[ALGORITHM] LEVEL3 2022 KAKAO BLIND RECRUITMENT - 양과 늑대 https://school.programmers.co.kr/learn/courses/30/lessons/92343# 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 주의할 점 어째서 인지는 모르겠으나 중복체크를 하지않은 단순 완전탐색으로도 풀리는 것 같습니다. 최악의 경우 피보나치 이상의 시간복잡도가 걸리게 됩니다. (한 가지를 선택하면 2개씩 늘어남 + 중복에 대한 순서 가지수) 최대 17개 이므로 단순 방문체크가 아닌 비트마스킹을 사용하여야 최악의 경우를 해결할 수 있습니다. 예제 [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, .. 2022. 12. 30.

티스토리툴바