잡담연구소

www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net IDEA 토마토가 다 익는데 걸리는 최소시간을 구하는 문제다 . 최소시간이라 BFS를 사용했다. 이전에 풀었던 문제들과 마찬가지로 최소시간,최소비용 등이라서 VISITED를 따로 쓰지않고 맵 자체를 거리로 업데이트해줬다. 1. 맨 처음부터 모두 다 익어있다면 0을 출력해야한다. -> 맨 처음 입력받으면서 익지않은 토마토 즉 0의 개수를 센다. 0의 개수가 0이라면 맨 처음부터 모두 익어있다는 뜻..

순열, 조합에 대한 더 자세한 설명은 👉 DFS로 순열 및 조합 구현 ( blahblahlab.tistory.com/28 ) (1) 순열 N개 중에 중복없이 M개를 고른다 & 수열사이 대소관계는 없다 (오름차순 혹은 내림차순) 👉 nPm 순열을 얘기하는거다 중복이 없어야 하므로 VISITED 배열을 이용해 방문여부를 따져야한다. 또 오름차순 내림차순과 같은 관계가 없으므로 항상 1부터 시작해도 된다. N을 입력받으면 1 ~ N 까지의 수로 순열을 만들면 되기 때문에 별다른 배열 없이 인덱스로만 구성하면 된다. #include #include using namespace std; int n, m; vectortemp; int visited[9] = { false }; void backtracking(int..

www.acmicpc.net/problem/1904 1904번: 01타일 지원이에게 2진 수열을 가르쳐 주기 위해, 지원이 아버지는 그에게 타일들을 선물해주셨다. 그리고 이 각각의 타일들은 0 또는 1이 쓰여 있는 낱장의 타일들이다. 어느 날 짓궂은 동주가 지원이 www.acmicpc.net IDEA 규칙만 찾으면 된다. 써보자 N = 1 1개 1 N = 2 2개 00 , 11 N = 3 3개 100 , 001, 111 N = 4 5개 1100 , 1001 , 0011, 0000, 1111 dp[n] = dp[n-1] + dp[n-2] (n > 2) 라는 점화식을 세울 수 있다. 그 후 문제의 조건에 맞게 15746으로 항상 나눠주면 된다. 코드 #include #include using namespac..

www.acmicpc.net/problem/9461 9461번: 파도반 수열 오른쪽 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 변의 www.acmicpc.net IDEA 스터디장님이 말하시길 DP는 점화식만 잘세워도 된다고 하셨다. 점화식의 기본은 일단 써보는 거라고 생각한다. 1 1 1 2 2 3 = 1 + 2 4 = 1 + 3 5 = 1 + 4 7 = 2 + 5 9 = 2 + 7 12 = 3 + 9 16 = 4 + 12 6번째 부터 자기 자신-1 번째 수와 자신 -5 번째 수의 합으로 이루어지는 걸 확인할 수 있다. 점화식을 세워보면 dp[n] = dp[n-1] + dp..

www.acmicpc.net/problem/2748 2748번: 피보나치 수 2 피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다. 이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n ≥ 2)가 www.acmicpc.net IDEA 피보나치 수열은 재귀로도 풀 수 있지만 이 문제는 재귀로 풀면 시간초과가 난다. 그 이전 수들이 모여 그 다음 수들을 만들 수 있으므로 DP로 풀 수 있다. DP의 기본격인 피보나치는 fibo[0] = 0 fibo[1] =1 fibo[n] = fibo[n-1] + fibo[n-2] (n >=2) 라는 점화식을 따라가면 된다. 문제에 90보다 작거나 같은 수라고 써있다..

www.acmicpc.net/problem/1992 1992번: 쿼드트리 첫째 줄에는 영상의 크기를 나타내는 숫자 N 이 주어진다. N 은 언제나 2의 제곱수로 주어지며, 1≤N ≤64의 범위를 가진다. 두 번째 줄부터는 길이 N 의 문자열이 N 개 들어온다. 각 문자열은 0 또는 www.acmicpc.net IDEA 이 전 문제와 달리 쿼드트리문제는 무조건 왼쪽위 > 오른쪽 위 > 왼쪽 아래 > 오른쪽 아래 순서를 지켜야한다. 한 쿼터 영역(예를 들어 왼쪽 위)에 대해 이중 for문을 돌며 모두 같은 숫자가 $n^{2}$개만큼 나왔는지 확인해준다. 한 쿼터 영역(예를 들어 왼쪽 위)이 모두 다 0 혹은 1 이 아니라면 압축 즉 한 번 더 4분할을 해주어야한다. 그렇기 떄문에 한 번 더 압축 해줄 때 전..