밤이 블로그

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#1182 부분집합의 합 * 문제https://www.acmicpc.net/problem/1182 * 풀이처음에는 조합을 이용해서 풀었습니다. (160ms)집합에서 1개를 고르는 경우, 2개를 고르는 경우, ...., N개를 고르는 경우 두번째 풀때는 집합의 각 원소의 2가지 경우에 대해(고르는 경우, 고르지 않는 경우)재귀 함수 호출로 답을 구하였습니다. (76ms) 주의할 점 : S가 0인 경우에는 공집합도 카운트 될 수 있음 * 나의 코드 https://github.com/stack07142/BOJ/blob/master/BOJ%231182_SumOfSubsets/src/Main.java import java.io.*; import java.util.StringTokenizer; /** * BO..

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#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) ..

BOJ#12969 ABC * 문제https://www.acmicpc.net/problem/12969 * 풀이풀이는 코드 주석으로 대신합니다. - 참고한 블로그 : https://fullalgorithmpanic.blogspot.kr/search?q=12969 * 나의 코드https://github.com/stack07142/BOJ/blob/master/BOJ%2312969_ABC/src/Main.java import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; /** * BOJ#12969 ABC * https://www.acmicpc.n..

BOJ#13398 연속합2 * 문제https://www.acmicpc.net/problem/13398 * 나의 코드 https://github.com/stack07142/BOJ/blob/master/BOJ%2313398_ContinuousSum2/src/Main.java import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; /** * BOJ#13398 연속합2 * https://www.acmicpc.net/problem/13398 */ public class Main { static final int MIN = -100000000; ..

BOJ#9376 탈옥 * 문제https://www.acmicpc.net/problem/9376ACM-ICPC > Regionals > Europe > Northwestern European Regional Contest > Benelux Algorithm Programming Contest > BAPC 2013 J번 * 풀이어려운 문제라고 생각합니다. 일단 맵을 상하좌우로 1칸씩 늘려줍니다. -> 이유 : 시도1 처럼 여러 시작점들을 어딘가에 저장해놓고 조사하는 것과, 외곽의 어느 한점을 시작점으로 잡고 조사하는 것은 차이가 없다.(문이 아니라면 cost가 없기 때문) 죄수 2명을 탈옥시키는 방법은 3가지가 있습니다. 1) 죄수 1이 죄수2를 데리고 바깥으로 나가는 경우 2) 죄수2가 죄수1을 데리고 바..

BOJ#14226 이모티콘 * 문제https://www.acmicpc.net/problem/14226 * 풀이 푸는데 고생했지만 재밌는 문제입니다.처음에는 1000개의 테스트케이스 중 11개만 틀렸는데, 원인을 찾기 쉽지 않았습니다. BFS 돌리면서 visited 배열로 정점을 중복 방문하지 않게 구현했는데, 이것이 실패 원인이었습니다. 왜냐하면 정점의 값이 같더라도 클립보드에 어떤 내용이 들어있는지에 따라 향후 탐색할 수 있는 정점이 달라지기 때문입니다. 따라서 visited 배열을 discovered 배열의 개념으로 바꾸고discovered 배열을 (기존)boolean[][] discovered = new boolean[정점] (변경)boolean[][] discovered = new boolean[..

BOJ#5014 스타트링크 * 문제https://www.acmicpc.net/problem/5014 * 풀이 생략 * 나의 코드 https://github.com/stack07142/BOJ/blob/master/BOJ%235014_Startlink/src/Main.java import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arrays; import java.util.PriorityQueue; import java.util.StringTokenizer; /** * BOJ#5014 스타트링크 * https://www.acmicpc.net/problem/5014 *..