티스토리챌린지3 [S4] 백준 31797 - 아~파트 아파트(Python3) https://www.acmicpc.net/problem/31797💡 해결과정 문제에 함정이 있었다. 아파트 술게임 특성상 절대 중간에 다른 층이 존재할 수 없다. 또, 독자적인 층을 부여할 수 없다.예를 들면 사람은 3명인데, 손을 가장 위로 뻗으며, "내 오른손은 100층" 뭐 이런식으로 말이다.하지만 이것은 실제 게임을 하는것이 아니라 문제이다. 고정관념에 휩싸였다간 이런 중간층 없이 높은 층을 불러버려 맞왜틀?을 외치게 만드는 문제다. 두 손의 높이를 편하게 left, right라고 부르겠다. 문제에서 주어지는 입력 조건은 참가자의 수 1,000일때 이 left, right가 9999, 10000일수도 있는 것이다.👀 풀이그래서 압축하듯이 정렬해서 풀면 된다.그래서 좌표 압축 문제가 이 문제.. 2024. 11. 14. [G4] 백준 10830 - 행렬 제곱 (Python3) https://www.acmicpc.net/problem/10830💡 해결방법분할 정복을 활용한 제곱으로 해결했다.👀 풀이x^n = x^{n/2} * x^{n/2} 을 이용한 풀이 방법이다.1629 곱셈에서 먼저 적용해볼 수 있다.🧾코드# 10830N, b = map(int, input().split())matrix = [list(map(int, input().split())) for _ in range(N)]I = [[0]*N for _ in range(N)]for i in range(N): I[i][i] = 1def square(mat, n): if n == 1: return matrix_multiplication(mat, I) elif n%2 == 0: .. 2024. 11. 11. [G5] 백준 1074 - Z (Python3) https://www.acmicpc.net/problem/1074💡 해결방법분할정복 알고리즘을 적용해서 문제를 해결했다.👀 풀이항상 2**(N*2) 매트릭스(r, c) 좌표 정보위 두 정보를 바탕으로 (r, c)가 몇 사분면에 있는지 파악해서 N 번만에 몇 번만에 방문하는지 계산한다.🧾 코드# 1074N, r, c = map(int, input().split())ans = 0while N: N -= 1 # 제1사분면 if r = 2**N: ans += 2 ** (N*2) c -= 2**N # 제2사분면 elif r = 2**N and c = 2**N and c >= 2**N: ans += 3*(2**(N*2)) r -= 2.. 2024. 11. 10. 이전 1 다음
