본문 바로가기

BOJ

BaekJoon 1912 연속합 2019. 1. 14. Link https://www.acmicpc.net/problem/1912 소스결과 2652 KB / 8 ms 출처 Backjoon 언어 C++ 17 분류 다이나믹 프로그래밍, 수학 설명 임의의 수열에 대해서 연속된 수의 합이 최대를 구하는 문제 예제만 보고 양수의 합을 구하다가 다음 수가 음수가 나오면 현재 까지의 합을 남기는 알고리즘을 만들었다가 오답 한개를 추가하고 시작했다. 위 예제에서 -35를 21 뒤에 놓는 형태로 바꾸면 문제에 숨겨진 함정이 나온다. 음수가 존재 한다고 해서 그 다음 수를 더했을 때 현재 까지의 합이 최대라는 보장이 없는 함정이 숨어 있다. DP Table 조금 변형을 가해서 현재까지의 합 + 다음 수의 합이 음수가 된다면 음수의 그 다음수가 양수여도 현재 합을 넘을 수 없는..
BaekJoon 11726 2xn 타일링 2019. 1. 14. Link https://www.acmicpc.net/problem/11726 소스결과 1984 KB / 0 ms 출처 Backjoon 언어 C++ 17 분류 다이나믹 프로그래밍 설명 2 x n 에 1 x 2, 2 x 1 타일로 채우는 방법의 수를 구하는 문제 DP의 기초를 다지기에 좋은 문제 먼저 결론부터 말하면 위 문제는 피보나치 수열의 형태를 띈다 2 x 5까지 경우의 수를 계산해 보면 피보나치 수열의 형태를 가진다 주의할 점은 경우의 수를 10007로 나눈 나머지를 구해야 한다. 피보니치 수열을 계산 한 후에 꼭 % 10007 연산을 통해 나머지를 저장하도록 하자 소스코드 #include using namespace std; const int MAX = 1000; int main() { int dp..
BaekJoon 2193 이친수 2019. 1. 14. Link https://www.acmicpc.net/problem/2193 소스결과 1984 KB / 0 ms 출처 Backjoon 언어 C++ 17 분류 다이나믹 프로그래밍 설명 0으로 시작하지 않으면서 1이 연속으로 두번 나오지 않는 N 자리의 이진수의 개수를 구하는 문제 각각의 경우를 계산 해보면 1 : 1 ( 1개 ) 2 : 10 ( 1개 ) 3 : 100 101 ( 2개 ) 4 : 1000 1001 1010 ( 3개 ) 5 : 10000 10001 10010 10100 1010 1 ( 5개 ) 피보나치 수열이다 아래의 점화식을 이용하자 dpTable[i] = dpTable[i - 1] + dpTable[i - 2]; ( 단 i > 1 ) 소스코드 #include using namespace st..
BaekJoon 1149 RGB 거리 2019. 1. 14. Link https://www.acmicpc.net/problem/1149 소스결과 2012 KB / 0 ms 출처 Backjoon 언어 C++ 17 분류 다이나믹프로그래밍 설명 이웃한 집과 같은색으로 칠하지 않으면서 모든 집을 칠할 때 드는 비용의 최솟값을 출력하는 문제 이전 집의 색을 기억해서 같은 색이면 그 색을 제외하고 최솟값을 구해 마지막까지 칠하는 경우 모든 경우에서 최솟값을 선택하는 그리디 알고리즘을 적용시키면 문제의 정답이 나오지는 않는다. 같은 값이 존재하는 경우 위치에 따라 다른 결과 값이 나올 수 있다는 점을 유의해야한다. 또한 매번 최선의 선택이 정답이 되지 않기 때문에 모든 경우에 대해서 검사를 해야 한다. DFS로 풀어나가면 시간 초과가 나온다. 점화식은 첫 번쨰 경우를 제외하고..
BaekJoon 1003 피보나치 함수 2019. 1. 14. Link https://www.acmicpc.net/problem/1003 소스결과 1984 KB / 8 ms 출처 Backjoon 언어 C++ 17 분류 다이나믹 프로그래밍 설명 문제에 나와 있는 소스 코드를 기반으로 0이 출력되는 경우와 1이 출력 되는 경우의 수를 출력하는 문제 저 함수를 직접 코드화 시켜서 printf 문 대신 0 인덱스를 1씩 추가시키면 시간 초과의 늪으로 들어간다 테스트 케이스 범위도 좁은 만큼 시간 제한도 0.25초로 매우 빡세다 점화식을 세우기 위해 0부터 4까지 계산해보면 0 : 1 0 1 : 0 1 2 : 1 1 3 : 1 2 4 : 2 3 이라는 결과를 바탕으로 0 이 출력되는 경우의 수와 1이 출력되는 경우의 수에 대해서 피보나치 수열처럼 구현하면 된다. 따라서 점화..
BaekJoon 2589 보물섬 2019. 1. 13. Link https://www.acmicpc.net/problem/2589 소스결과 2000KB / 100 ms 출처 BackJoon, 한국정보올림피아드 시,도 본선 지역본선 2005 초등부 3번 언어 C++17 분류 BFS 설명 어딘가에 숨어있는 보물의 최단거리의 최대 경우를 탐색하는 문제 DFS는 시도해보지 않았지만 경우의 수가 커질 경우 DFS는 시간초과가 예상이 된다. 모든 육지에 대해서 BFS를 진행해야한다. 20 by 20에서 모든 위치를 L로 초기화 시켜서 돌려보았더니 1초를 살짝 넘은후 결과가 나와서 Timeout을 예상했지만 시간이 1초인 만큼 최대 결과도 맞춰 놓은것 같다. BFS를 무작정 많이 시도 하면 된다. 땅의 위치를 배열에 저장한 후 풀면 n * m 만큼 반복문을 안돌리고 땅의..
BaekJoon 11559 Puyo Puyo 2019. 1. 13. Link https://www.acmicpc.net/problem/11559 소스결과 1998 KB / 0 ms 출처 Backjoon, 2015 연세대학교 프로그래밍 경시대회 C번 언어 C++ 17 설명 기억속 뿌요뿌요 ( 출처 : Google - 뿌요뿌요 2 ( Puyo Puyo 2) ) 에서 터지는 경우를 계산해보자 조건이 몇개 걸려있어서 약간 까다로웠던 문제 얼마나 연결될지 몰라서 일단은 BFS로 풀었다. 기존 문제들과 다른 점이라면 최소 4개가 연결 되어 있어야 하기 때문에 무턱대고 방문 했다고 값을 . 으로 바꿔주면 안됬다. 일단은 연결 되어있는 개체 수를 저장하고 나중에 그 값이 4가 넘어가는 라벨에 한해서만 터진 경우로 바꿔 주어야 한다. 또한 지워진 경우 위의 값을 당겨야 하기 때문에 정리..
BaekJoon 2292 벌집 2019. 1. 13. Link https://www.acmicpc.net/problem/2292 소스결과 2376 KB / 0 ms 출처 BackJoon, ACM-ICPC Seoul National Internet Competition 2004 B번 언어 C++ 17 분류 다이나믹 프로그래밍, 수학 설명 입력받은 숫자 n이 1을 포함하여 몇번째 외곽에 존재 하는지 푸는 문제 친구가 어떻게 풀지 물어봐서 풀어본 문제 이번 문제는 푸는 방법이 여럿 존재한다. 점화식이 너무 선명하다 1을 기준으로 오른쪽 대각선의 값이 6 * i 를 더한 값이 계속 반복되기 때문 반복문을 통해서 푸는게 가장 짧은 코드이지만 지금은 DP에 대해서 계속 공부하고 있는 중이기에 DP로 풀었다. 알고리즘 1. 외곽의 최대 값을 입력할 배열 dp를 생성 및..

티스토리툴바