본문 바로가기

Solved.ac/Class 35

[BOJ] 백준 1697번: 숨바꼭질 www.acmicpc.net/problem/1697 1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 �� www.acmicpc.net 순간이동이 현재 좌표에 2배까지 가능하므로 최대 배열 크기를 20만으로 잡고, dp[i]는 i 좌표로 이동하는데 걸리는 최소 시간이라고 보면 아래 코드와 같이 해결 가능합니다. 먼저 n보다 작은 좌표 위치는 -1 로 이동할 수밖에 없으므로 최소 시간은 n - i로 초기화해주고 과정 1. 반복적으로 +1 이동하는 경우 과정 2. 2배 이동하는 경우 두 가지 경우에 대하여 최솟값을 .. 2020. 9. 7.
[BOJ] 백준 14500번: 테트로미노, 브루트포스, 필터링 www.acmicpc.net/problem/14500 14500번: 테트로미노 폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변� www.acmicpc.net 주어진 블록모양에 대하여 회전, 반전 한 상대적인 좌표 위치를 필터로 저장하여 (아래 첨부했으니 고통을 덜어가세요.) 모든 좌표에 대하여 총 19가지의 필터를 씌워 필터내의 숫자의 합 중 제일 큰것을 찾아가면 됩니다. int filter[19][2][4] = { {{0,0,1,1},{0,1,0,1}}, {{0,0,0,0},{0,1,2,3}}, {{0,1,2,3},{0,0,0,0}}, {{0,1,2,2},{0,.. 2020. 9. 7.
[BOJ] 백준 1676번: 팩토리얼 0의 개수 www.acmicpc.net/problem/1676 1676번: 팩토리얼 0의 개수 N!에서 뒤에서부터 처음 0이 아닌 숫자가 나올 때까지 0의 개수를 구하는 프로그램을 작성하시오. www.acmicpc.net N! 은 1x2x3x4 x... N으로 곱하는 과정에서 10의 배수가 생길 때마다 0이 생깁니다. 다시 해석해보면 N!을 곱하는 전체 과정을 소인수 분해하여 2와 5의 개수를 찾으면 맨뒤에 오는 연속된 0의 개수를 알 수 있습니다. 좀 더 간단화시키면 2의 배수는 5의 배수보다 항상 많으므로 N! 를 소인수 분해하여 5의 개수를 찾으면 됩니다. 5, 10, 15, 20, .... 은 5를 1개 가지고 있습니다. 25, 50, 75, .... 는 5를 2개 가지고 있습니다. 125, 250, 375.. 2020. 9. 7.
[BOJ] 백준 11726번: 2xn 타일링, 타일링 문제 www.acmicpc.net/submit/11726/21279055 로그인 www.acmicpc.net 타일링 문제는 동적 계획법을 접하면 입문 문제로 간단한 점화식으로 풀리는 문제입니다. 타일은 1x2 크기와 이것을 회전한 2x1 타일이 있으며, 길이 n이 주어질 때 2 x n 직사각형을 채울 수 있는 경우의 수를 찾아야 합니다. 아래는 n이 각각 1, 2, 3 인 경우를 보여줍니다. 각 경우에서 보면 빨간 블록은 이전 단계들의 블록 모양이며 파란색은 현재 단계에 새로 추가된 블록입니다. 여기까지만 보면 점화식을 d[i] = d[i-1] + d[i-2]로 유추해볼 수 있습니다. 좀더 정확하게 알아보기 위해 n이 4인 경우를 보면 n이 2인 경우 + n이 3인 경우의 합이 됩니다. 점화식은 피보나치 형태.. 2020. 9. 7.

티스토리툴바