본문 바로가기

백준

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를 생성 및..
BaekJoon 10026 적록색약 2019. 1. 13. Link https://www.acmicpc.net/problem/10026 소스결과 1996 KB / 0 ms 출처 Backjoon, USACO March 2014 Contest Bronze 3번 언어 C++ 17 분류 BFS DFS 설명 정상인이 봤을때의 그룹 수와 적록색약인 사람이 봤을 떄 그룹 수를 출력하는 문제 기존 문제와 다른점은 동일시 해야 하는 경우가 존재한다는 것 정상인 입장의 그룹 수는 R G B로 나누어서 그룹 수를 구하면 되지만 적록색약인 경우 R 이나 G일때 R , G를 전부 같은 색으로 판단해야 한다는 것이다. 방법은 2가지가 존재한다. 먼저 정상인 기준의 값을 전부 받은 후 R과 G를 전부 B가 아닌 특정 값으로 전부 바꾼 배열을 따로 만들어도 된다. 다른 방법은 BFS를 사용..
BaekJoon 1699 제곱수의 합 2019. 1. 12. Link https://www.acmicpc.net/problem/1699 소스결과 2392 KB / 56 ms 출처 BackJoon, ACM-ICPC 언어 C++ 17 분류 다이나믹 프로그래밍 설명 어떤 자연수 N에 대하여 제곱수의 합으로 표현 할 때, 제곱수의 최소 개수를 구하는 문제 간단하게 생각하면 가장 큰 제곱수를 빼면서 0 ~ 3 사이의 결과가 나올 때 그 값을 더해 주면 된다. 위 알고리즘을 구현한 결과는 틀렸습니다. 알고보니 32 같은 반례가 존재했다. 위 알고리즘대로라면 32 = 25 + 9 + 1 + 1 로 4번이 나오지만 정답은 16 + 16 으로 2 이다. 결과에 대해서 검증하는 과정이 필요하다. 알고리즘 1. n 을 입력 받는다. 2. DP Table을 초기화 한다. 2 - 1 현..
BaekJoon 11057 오르막수 2019. 1. 12. Link https://www.acmicpc.net/problem/11057 소스결과 2024 KB 0 ms 출처 BackJoon 언어 C++17 분류 다이나믹 프로그래밍 설명 1234, 55557 과 같이 모든 자리의 수가 다음 자리 수보다 같거나 큰 수인 경우의 수를 헤아리는 방법 최대 입력이 1000 이고 개수를 10007로 나눈 나머지를 구해 한다. long long int로 최대 크기까지 늘려도 정답은 오답으로 나온다. 어짜피 10007로 나누어야 한다는 조건이기에 모든 경우의 수에서 10007로 나눈 나머지를 dp의 값으로 사용 해도 된다. % 연산자의 특성상 ( a + b ) % c = ( ( a % c ) + ( b % c ) ) % c이기 떄문에 합을 구하고 % 연산자를 넣어주어야 한다...
BaekJoon 1010 다리놓기 2019. 1. 12. Link https://www.acmicpc.net/problem/1010 소스결과 1988 KB 16ms 출처 BackJoon 언어 C++ 17 분류 다이나믹 프로그래밍 설명 만들 수 있는 다리의 총 합을 구하는 문제 DFS 처럼 생각해서 가지치기를 했더니 최대 다리 개수를 놓았을 경우에 너무 오래 걸렸다. 점화식은 간단하다 RES[i][j] = RES[i-1][j] + RES[i][j-1] 예외 조건은 순서가 역전 되지 않게 만들어 주기만 하면 된다. 어렵게 생각하면 밑도 끝도 없이 어렵다.. 간단하게 생각하자 알고리즘 1. DP Table을 초기화한다. 2. 입력값 n, m 에 대하여 DP Table [ n -1 ] [ m - 1 ] 을 출력한다. 소스코드 #include using namespac..
BaekJoon 1932 정수 삼각형 2019. 1. 12. Link https://www.acmicpc.net/problem/1932 소스결과 2968 KB 32 ms 출처 BackJoon, IOI 1994 1번 언어 C++ 17 분류 다이나믹 프로그래밍 설명 DP에 대해서 공부해보자! 나올 수 있는 모든 경우의 수를 계산한다.! 하지만 옛 결과를 가지고 계산을 한다! 위 피라미드 문제가 DP에 대해서 학습하기는 편한거 같다. 위의 값에 대해서 왼쪽을 더했을때, 오른쪽을 더했을 때의 값 중 큰 값을 넣으면 된다. 눈에 보이는 대로 구현하자! 알고리즘 1. 피라미드를 입력 받는다. 2. 1번 줄부터 각 위치의 왼쪽, 오른쪽 값의 합을 더했을때 더 큰 경우를 현재 위치의 값으로 삼는다. 3. 피라미드중 가장 큰 값을 출력한다. ( 밑의 소스코드는 모든 배열을 탐색 ..
BaekJoon 10989 수 정렬하기 3 2019. 1. 12. Link https://www.acmicpc.net/problem/10989 소스결과 1136 KB / 2444 ms 출처 Backjoon 언어 C 분류 정렬 설명 개수가 많아서 시간제한이 3초다, 근데 메모리는 고작 8 MB 배열을 전부 저장하게 되면 메모리는 견디지 못한다. 메모리가 넉넉했더라면 Quick Sort로 구현 해도 정답이 되겠지만 위 문제는 Quick Sort로 구현하는게 아니다. 중복되는 수가 존재하기 때문에 그 수의 개수만 알고 있으면 되고, 그 수를 순서대로 출력하는 Counting Sort를 구현하는 문제이다. 다른 Sorting과는 다르게 중복 되는 값이 존재하는 경우에 사용하는 Sorting 방법이다. 주 핵심은 중복되는 값의 개수를 저장하는 것이다. 알고리즘 1. 값을 입력 ..

티스토리툴바