밤이 블로그

BOJ#9084 동전 * 문제https://www.acmicpc.net/problem/9084 * 풀이참고한 블로그 : http://wootool.tistory.com/177http://blog.naver.com/PostView.nhn?blogId=occidere&logNo=220793012348http://heygyun.tistory.com/46 동적계획법의 개념(복잡한 문제를 여러 하위 문제로 나누어 푼다)을 잘 생각해봅시다.dp[i] : 주어진 동전을 가지고 금액 i를 만드는 경우의 수 예를 들어 목표 금액이 30원이고, 동전이 5원, 10원짜리가 있을 때 일단은 5원짜리만 있다고 가정했을 때 dp[30] : 5원짜리로 30원을 만드는 경우의 수이제 10원짜리 동전을 추가해보자. dp[30] : 3..

BOJ#14501 퇴사 * 문제https://www.acmicpc.net/problem/14501 * 풀이2017년 상반기 삼성전자 SW 역량테스트 기출문제입니다. dp 문제입니다. 각 경우(상담)에 대해 상담하는 경우, 상담하지 않는 경우 2가지 경우로 나눌 수 있습니다. 정의 및 점화식dp[idx] : 날짜가 idx 일 때, 이후 얻을 수 있는 금액의 최대값dp[idx] = max(dp[idx+1], dp[idx + T[idx]] + P[idx]) * 나의 코드https://github.com/stack07142/BOJ/blob/master/BOJ%2314501_Retire/src/Main.java import java.io.BufferedReader; import java.io.IOException..

BOJ#1937 욕심쟁이 판다 * 문제https://www.acmicpc.net/problem/1937 * 풀이dp + 탐색 * 나의 코드https://github.com/stack07142/BOJ/blob/9fb5631acdf38f48b28e2ee02bc0ac4a6a4c3a7f/BOJ%231937_GreedyPanda/src/Main.java import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; /** * BOJ#1937 욕심쟁이 판다 * https://www.acmicpc.net/problem/1937 */ public class..

BOJ#2666 벽장문의 이동 * 문제https://www.acmicpc.net/problem/2666 * 풀이1. 문제 이해벽장문을 이동을 열려있는 문이 이동한다는 것으로 바꿔서 생각해봅시다. 훨씬 편하게 문제를 이해할 수 있습니다.열려있는 문은 항상 2개 뿐이므로 하나를 F, 나머지를 S라고 해봅시다. 열려있는 문이 이동하므로 2가지 경우가 발생합니다. 1) F가 이동하는 경우2) S가 이동하는 경우 2. 풀이 설계이 문제는 벽장문의 사용 순서에 따라 탐색이 진행되고, 완전 탐색이 되어야 합니다.이 과정에서 필요한 것, 저장시켜야 하는 것, 변화하는 것들을 이용하여 dp를 정의하고 점화식을 세워보면 (정의)dp[pos1][pos2][idx] : 열린문 F의 위치가 pos1이고 열린문 S의 위치가 po..

BOJ#5557 1학년 * 문제https://www.acmicpc.net/problem/5557 * 풀이- dp[i][sum] : i번째까지 진행했을 때, 합이 sum인 경우의 개수- 구하는 값은 dp[N-2][A[N-1]]- solve(idx, sum) : dp[idx][sum]을 구하는 함수 * 나의 코드https://github.com/stack07142/BOJ/blob/master/BOJ%235557_FirstGrader/src/Main.java import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; /** * BOJ#5557 ..

BOJ#2098 외판원 순회 * 문제https://www.acmicpc.net/problem/2098 * 풀이dp 문제입니다. (주의점, 힌트)1. 사이클이므로 어느 점을 시작점으로 잡아도 상관없다.2. 마을 방문 여부를 매개변수로 넘겨주기 위해서는 ? 비트마스크를 사용하자.3. 시간 복잡도 : O(N^2 * 2^N) * 나의 코드https://github.com/stack07142/BOJ/blob/master/BOJ%232098_TSP/src/Main.java import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arrays; import java.util.St..

BOJ#9520 NP-Hard * 문제https://www.acmicpc.net/problem/9520 * 풀이- 규칙 : 번호가 K인 도시를 방문하려면, K보다 작은 번호를 가진 모든 도시를 K번을 방문하기 전에 모두 방문하거나, 방문한 후에 모두 방문해야 한다.즉, K보다 번호가 작은 도시 중 하나를 K번 이전에 방문하고, 다른 하나를 K번 이후에 방문하면 안된다. 위 규칙을 만족하는 방문 수열은 아래와 같이 만들 수 있습니다. 맨 처음 1번 도시를 방문 : {1}그 다음 2번 도시는 수열의 왼쪽 또는 오른쪽에 들어갈 수 있습니다 : {2, 1}, {1, 2}그 다음 3번 도시는 수열의 왼쪽 또는 오른쪽에 들어갈 수 있습니다 : {3, 2, 1}, {2, 1, 3}, {3, 1, 2}, {1, 2, ..

BOJ#12101 1, 2, 3 더하기 2 * 문제https://www.acmicpc.net/problem/12101 * 풀이dfs로 풀었습니다. dfs를 돌리면 자연스럽게 오름차순으로 결과가 나옵니다.풀이는 쉽기 때문에 생략합니다. dp로 다시 푼 후 업데이트 예정. * 나의 코드https://github.com/stack07142/BOJ/blob/master/BOJ%2312101_Sum123_2/src/Main.java import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; /** * BOJ#12101 1, 2, 3 더하기 2 * ..

BOJ#11048 이동하기 * 문제https://www.acmicpc.net/problem/11048 * 풀이풀이는 생략합니다.dp 초기값만 주의할 것. * 나의 코드https://github.com/stack07142/BOJ/blob/master/BOJ%2311048_Move/src/Main.java import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arrays; import java.util.StringTokenizer; /** * BOJ#11048 이동하기 * https://www.acmicpc.net/problem/11048 */ public class..

BOJ#11058 크리보드 * 문제https://www.acmicpc.net/problem/11058 * 풀이- dp[i] : 버튼을 i번 눌렀을 때, 화면에 출력할 수 있는 A의 최대 개수 dp를 위와 같이 정의하고, 문제를 분석하면서 몇가지 성질을 찾아보았습니다. 0. i가 클수록 dp[i]가 무조건 크다. 1. i가 커질수록 인접한 dp값들의 차이가 커진다. 2. dp[i]의 값은 무조건 dp[i-3] * 2보다 무조건 크거나 같다. 또한 dp[i-3]의 값은 dp[i-6] * 2 보다 무조건 크거나 같다.... 3. i가 일정 수준 이상이면(7이상), 이제는 A를 하나 추가하는 버튼은 필요가 없다. 복사-붙여넣기 동작만 하는 것이 A를 최대로 출력할 수 있다. 4. dp[i] 값은 i번째에 1) ..