DP

🔗 문제 SW Expert Academy SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 🖍 풀이 DFS는 시간초과고 BFS이라고 생각해서 풀면 오답이다. (경험담) 왜냐하면 생각해보면 map의 좌표 (x, y)까지 오는 경로는 다양하다. 가는 길이 0, 1로만 이루어진 것이 아니기 때문에 첫 방문이 최소 경로라고 단정지을 수 없다. 그래서 상하좌우로 이동하면서 (x, y)까지 걸린 시간을 계속해서 갱신해주어야 한다. visited[x][y]로 재방문를 판단하기는 하지만 그냥 갱신인지 신규인지만 판단하는 용도로 사용해줬다. 다익스트라의 개념을 알고 있으면 내 풀이를 이해하는데 도움됨 💾 소스 #include #..

🔗 문제 14501번: 퇴사 14501번: 퇴사 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. www.acmicpc.net 🖍 풀이 일을 했을 경우와 일을 하지 않았을 경우로 상황을 나눠 생각할 수 있다. i 날에 일을 한 경우: i + T[i] 에 수익이 전에 벌어 놓은 돈 + P[i] 이 된다. i 날에 일을 하지 않을 경우: i+T[i]날 수익에 변동이 없다. 이걸 재귀함수로 짠다면? 간단하게 생각하면 완전 탐색할 수 있다. void solve(int days, int profit) { if(days == N+1) { return; } solve(days + T[days], profit + P[days]); solve(days + 1, profit) } 하지만 재귀함수는 호출된 함수 메모..

🔗 문제 16500번: 문자열 판별 16500번: 문자열 판별 첫째 줄에 길이가 100이하인 문자열 S가 주어진다. 둘째 줄에는 A에 포함된 문자열의 개수 N(1 ≤ N ≤ 100)이 주어진다. 셋째 줄부터 N개의 줄에는 A에 포함된 단어가 한 줄에 하나씩 주어진다. A에 www.acmicpc.net 🖍 풀이 만든 예시 softcorn 3 softc corn soft S의 문자열 하나하나 A목록과 대조 시키며 풀면 된다. idx 0 1 2 3 4 5 6 7 S s o f t c o r n A[0] s o f t A[1] c o r n A[2] s o f t c s[0]의 s로 시작하는 단어가 있는지 A를 뒤지고 s[1]의 o로 시작하는 단어가 있는지 A를 뒤지고 … 이걸 s.size()만큼 반복한다. 이..