[BaekJoon] #11726 - 2×n 타일링 [Java][C++]
문제 링크 1. 아이디어 다이나믹 프로그래밍을 활용해서 해결할 수 있는 전형적인 문제로 dp 테이블은 해당 가로 길이로 만들 수 있는 타일링의 수로 정의하면 된다. dp[i]는 가로 길이 i인 타일링의 수로 가로 길이 i인 타일링들은 가로 길이 i - 2인 타일링들에서 1×2 타일 두 개를 위아래로 쌓아 오른쪽 끝에 붙이거나, 가로 길이 i ...
문제 링크 1. 아이디어 다이나믹 프로그래밍을 활용해서 해결할 수 있는 전형적인 문제로 dp 테이블은 해당 가로 길이로 만들 수 있는 타일링의 수로 정의하면 된다. dp[i]는 가로 길이 i인 타일링의 수로 가로 길이 i인 타일링들은 가로 길이 i - 2인 타일링들에서 1×2 타일 두 개를 위아래로 쌓아 오른쪽 끝에 붙이거나, 가로 길이 i ...
문제 링크 1. 아이디어 $A$시 $B$분 $C$초에서 $D$초 후의 시각을 찾는 문제로 시는 24 단위로, 분과 초는 60 단위로 다음 단위로 올림이 되는 점을 활용해서 몫과 나머지 연산으로 해결했다. 2. 복잡도 접근 시간 공간 풀이 ...
문제 링크 1. 아이디어 정수 삼각형에서 특정 위치까지 내려왔을 때 선택된 수의 합의 최댓값은 바로 위층의 왼쪽 대각선까지 올 때 선택할 수 있었던 수의 합과 오른쪽 대각선까지 올 때 선택할 수 있었던 수의 합 중 더 큰 값에 현재 위치의 수를 더하면 된다. 양 끝 칸은 윗층에서 올 수 있는 대각선이 하나뿐이지만 수가 모두 0 이상이므로 없는...
문제 링크 1. 아이디어 최소 힙을 구현하면 되는 문제로 우선순위 큐 자료구조를 활용했다. 2. 복잡도 접근 시간 공간 풀이 $O(N \log N)$ $O(N)$ ($N$ = 입력값 n) 3. 코드 풀이...
문제 링크 1. 아이디어 최대 힙을 구현하면 되는 문제로 우선순위 큐 자료구조를 활용했다. 2. 복잡도 접근 시간 공간 풀이 $O(N \log N)$ $O(N)$ ($N$ = 입력값 n) 3. 코드 풀이...
문제 링크 1. 아이디어 자연수 $N$에 대해 1과 자기 자신을 제외한 모든 약수가 주어졌을 때 $N$을 구하는 문제로 약수는 쌍을 이루어서 나오기 때문에 가장 작은 약수와 가장 큰 약수의 곱으로 $N$을 찾을 수 있다. 2. 복잡도 접근 시간 공간 ...
문제 링크 1. 아이디어 괄호가 짝이 맞는지 판단하는 문제로 스택 자료구조를 활용해 여는 괄호는 스택에 넣고 닫는 괄호는 스택에 여는 괄호가 있는지 판단하면 된다. 여는 괄호가 더 많아 스택이 비지 않는 경우에 주의해야 한다. 2. 복잡도 접근 시간 공간 ...
문제 링크 1. 아이디어 소괄호와 대괄호가 섞인 문자열에서 괄호쌍이 서로 맞는지 판단하는 문제로 스택 자료구조를 활용해 여는 괄호는 스택에 넣고 닫는 괄호는 스택의 최근 괄호와 맞는 쌍인지 판단하면 된다. 여는 괄호가 더 많아 스택이 비지 않는 경우에 주의해야 한다. 2. 복잡도 접근 시간 ...
문제 링크 1. 아이디어 오늘이 일요일일 때, $X$일 후가 화요일인지 판단하는 문제로 7일 단위로 다시 일요일이 되므로 $X$를 7로 나눈 나머지가 2면 화요일이다. 2. 복잡도 접근 시간 공간 풀이 $O(1)$ $O(1)$ ...
문제 링크 1. 아이디어 1개에 $A$엔인 사탕 $B$개와 $C$엔인 봉투의 가격의 총합으로 $A \times B + C$로 간단하게 구할 수 있다. 2. 복잡도 접근 시간 공간 풀이 $O(1)$ $O(1)$ ...