Posts

백준 9095번 바로가기 나의 풀이 import sys read = sys.stdin.readline arr = [1,2,4] + [0]*12 for i in range(12): arr[i+3] = arr[i+2] + arr[i+1] + arr[i] for _ in range(int(read().strip())): print(arr[int(read().strip())-1]) CODE REVIEW 처음 아이디어는 중복조합에서 칸막이를 세우는 방법을 생각했는데, 1, 2, 3만 사용 가능해서 적용하기에 쉽지 않았다. 사실 n<=11이기 때문에 11까지 직접 노가다로 구하는 방법도 있겠지만, 코딩 문제 풀이이기 때문에 다른 방법을 생각해보았다. n이 1부터 6까지에 대한 $a_{n}$ 수열을 구해다가, $a_{n+3} = a_{n+2} + a_{n+1} + a_{n}$ 규칙성을 발견했다. 이 점화식을 분석해보면, (n+3)개의 경우의 수는 (n+2)개에 1을 오른쪽에 붙인 경우 + (n+1)개에 2을 오른쪽에 붙인 경우 + (n)개에 3을 오른쪽에 붙인 경우의 합이다. 반대쪽에 붙이는 경우, case가 겹치기 때문에 중복 counting 되어 안된다.

백준 9251번 바로가기 나의 풀이 # 입력 import sys read = sys.stdin.readline A, B = read().strip(), read().strip() n, m = len(A), len(B) LCS = [[0] * (m + 1) for _ in range(n + 1)] # 처리 - LCS 알고리즘 이용 for i in range(1, n + 1): for j in range(1, m + 1): if A[i - 1] == B[j - 1]: LCS[i][j] = LCS[i - 1][j - 1] + 1 else: LCS[i][j] = max(LCS[i - 1][j], LCS[i][j - 1]) print(LCS[n][m]) CODE REVIEW 백준 17218번 문제에서 배운 LCS 알고리즘을 이용한 문제. 17218번은 이 문제의 문자열 ver. 변형이라고 볼 수 있다. (n*m) matrix에 경로찾기처럼 숫자를 더해나가며 채워가면 최장 공통 부분 수열의 최대 길이는 마지막 요소에 저장된다. REFERENCES 그림으로 이해하는 LCS 알고리즘

백준 번 바로가기 첫 번째 풀이 # 입력 import sys read = sys.stdin.readline A, B = read().strip(), read().strip() n, m = len(A), len(B) LCS = [[0] * (m + 1) for _ in range(n + 1)] LCS2 = [[''] * (m + 1) for _ in range(n + 1)] # 처리 - LCS 알고리즘 이용 for i in range(1, n + 1): for j in range(1, m + 1): if A[i - 1] == B[j - 1]: LCS[i][j] = LCS[i - 1][j - 1] + 1 LCS2[i][j] = LCS2[i - 1][j - 1] + A[i-1] else: LCS[i][j] = max(LCS[i - 1][j], LCS[i][j - 1]) if LCS[i-1][j] > LCS[i][j-1]: LCS2[i][j] = LCS2[i-1][j] else: LCS2[i][j] = LCS2[i][j-1] print(LCS[n][m]) print(LCS2[n][m]) 두 번째 풀이 # 입력 import sys read = sys.stdin.readline A, B = read().strip(), read().strip() n, m = len(A), len(B) LCS = [[0] * (m + 1) for _ in range(n + 1)] # 처리 - LCS 알고리즘 이용 for i in range(1, n + 1): for j in range(1, m + 1): if A[i - 1] == B[j - 1]: LCS[i][j] = LCS[i - 1][j - 1] + 1 else: LCS[i][j] = max(LCS[i - 1][j], LCS[i][j - 1]) print(LCS[n][m]) ans = '' x, y = n, m while x > 0 and y > 0: if LCS[x][y] == LCS[x - 1][y]: x -= 1 elif LCS[x][y] == LCS[x][y - 1]: y -= 1 else: ans += A[x-1] x -= 1 y -= 1 print(ans[::-1]) CODE REVIEW 백준 9251번 - LCS의 연장선 격인 문제. 첫 번째 풀이의 경우 시간초과 에러가 발생했는데, string을 저장하는 과정 자체가 시간이 오래 소요되는 것으로 판단된다. 두 번째 풀이에서는 LCS2 matrix을 사용하지 않고, LCS을 그대로 사용하면서 역추적 해나가는 방식을 택했다. 역추적 해가면서 대각선으로 움직이는 시점의 문자를 더해가며 문자열을 찾아낼 수 있다.

백준 9375번 바로가기 나의 풀이 import sys from collections import Counter read = sys.stdin.readline for _ in range(int(read().strip())): closet = [] for _ in range(int(read().strip())): temp = read().split() closet.append(temp[1]) closet = Counter(closet) ans = 1 for c in closet.values(): ans *= (c+1) print(ans-1) CODE REVIEW (종류별 갯수 + 1)을 모두 곱해준 뒤에 1을 빼주면 원하는 값이 나온다. collections 모듈의 Counter 클래스를 이용하여 편하게 해결했다.

백준 9461번 바로가기 나의 풀이 # 입력 import sys read = sys.stdin.readline arr = [1,1,1,2,2] + [0]*100 # 처리 for i in range(99): arr[i+5] = arr[i+4] + arr[i] for _ in range(int(read().strip())): print(arr[int(read().strip())-1]) CODE REVIEW 규칙이 잘 안보이길래 n이 1부터 12일 때까지 P(N)값을 구해놓고 규칙을 찾아보았다. 점화식으로 $a_{n+5} = a_{n+4} + a_{n}$ 과 같다. 여러 번 불러와야 하므로 105개 정도의 요소를 가진 arr을 미리 구해놓는게 빠르다.