No. 17299
1. Problem
2. Others' Solutions
- 테트로미노로 표현 가능한 모든 도형의 모양을 생각해봄 -> 19개
- 각각의 모형을 4x4 보드에서 (0,0)을 기준으로 좌표로 표시
- 주어진 board 에서 (0,0) 부터 (n,m) 까지 한칸씩 옮기면서 모두 판단
import sys
import math
tetrominos = [
[(0,0),(0,1),(0,2),(0,3)], # ㅡ
[(0,0),(1,0),(2,0),(3,0)], # ㅣ
[(0,0),(1,0),(0,1),(1,1)], # ㅁ
[(0,0),(1,0),(2,0),(2,1)], # ㄴ
[(1,0),(1,1),(1,2),(0,2)],
[(0,0),(0,1),(1,1),(2,1)],
[(0,0),(0,1),(0,2),(1,0)],
[(2,0),(2,1),(1,1),(0,1)],
[(0,0),(0,1),(0,2),(1,2)],
[(0,0),(0,1),(1,0),(2,0)],
[(0,0),(1,0),(1,1),(1,2)],
[(0,0),(1,0),(1,1),(2,1)], # ㄴㄱ
[(1,0),(1,1),(0,1),(0,2)],
[(0,1),(2,0),(1,1),(1,0)],
[(0,0),(0,1),(1,1),(1,2)],
[(0,1),(1,0),(1,1),(1,2)], # ㅗ
[(1,0),(0,1),(1,1),(2,1)],
[(0,0),(0,1),(0,2),(1,1)],
[(0,0),(1,0),(1,1),(2,0)]]
n,m = map(int, sys.stdin.readline().rstrip().split())
board = []
result = 0
for _ in range(n):
board.append(list(map(int,sys.stdin.readline().rstrip().split())))
for i in range(n): # 열 이동
for j in range(m): # 행 이동
for tetromino in tetrominos: # 19개의 테트로미노에서 하나씩 선택
temp = 0
for dx,dy in tetromino: # 기준 좌표 board[i][j]에서 테트로미노에 맞게 dx,dy 좌표 더해줌
ix = i + dx
jy = j + dy
if 0 <= ix < n and 0 <= jy < m:
temp += board[ix][jy]
else: # 범위를 넘어가면 result 로 채택될 수 없도록 -inf 값 지정
temp = -(math.inf)
break
if result < temp: # 테트로미노 하나씩 마다 result 갱신가능 여부 판단
result = temp
print(result)
- DFS 알고리즘을 이용한 풀이법은 추후 공부후 풀어볼 예정
3. Learned
- 도형(모양) 문제는 좌표를 기준으로 하는 경우가 많음 (2차원 리스트)
- 해당 도형(문양)을 (0,0) 기준으로 표현하고 기준 좌표만 달리하여 표현하는 원리를 이용하자
- 주어진 board의 범위를 벗어난 경우에 해결방법
- 위에 처럼 대소비교로 분기
- 행열 3씩 더 추가한 board에다가 -inf 값을 넣어서 result 로 채택되지 않게함
- except 를 이용하여 continue
No. 1748
1. Problem
2. My Solution
- 1 자리수는 1씩 증가, 2 자리수는 2씩 증가 ... 9 자리수는 9씩 증가
- 1~9 까지 9개 존재, 10~99 까지 90개 존재, 100~999 까지 900개 존재 ...
- 만약 120 이면 (1 자리수의 개수 * 1) + (2 자리수의 개수 * 2) 값에 (120-99) * 3 값을 더함
- 위 규칙을 이용하기 위해 (자릿수 마다 존재하는 모든 수의 개수 * 각 자리수 값)을 미리 저장
import sys
n = sys.stdin.readline().rstrip()
count = [0,9,180,2700,36000,450000,5400000,63000000,720000000]
res = 0
if len(n) == 1:
print(n)
else:
for i in range(1,len(n)):
res += count[i]
res += (int(n) - int('9' * (len(n) - 1))) * len(n)
print(res)
3. Others' Solutions
- 9, 90, 900 ... 을 for 문을 이용해서 생성하기 위해 (10 * i) 이용
- 120 에서 3자리수의 개수를 위해 120 - 99 가 아닌 120 - 100 + 1 원리 이용
import sys
n = sys.stdin.readline().rstrip()
res = 0
for i in range(len(n)-1):
res += 9 * (10 ** i) * (i+1)
print(res + ((int(n) - (10 ** (len(n)-1)) + 1) * len(n)))
4. Learned
- 9, 90, 900, 9000 을 for 문으로 생성하기 위해 (10 ** i) 원리를 이용하면 됨
No. 15649
1. Problem
2. My Solution
- 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열 = 순열
- 첫 번째 방법
- res.append(arr) 를 이용해서 arr 를 삽입하면 res 리스트에 arr 의 값이 삽입되는 것이 아니라 res[index]가 arr 를 참조하는(가리키는) 원리임
- 따라서, arr 값이 바뀔 때 마다 res 리스트의 요소들(res[index]) 또한 바뀐 값을 가르키게됨
import sys
def permutation(level):
if level >= m:
res.append(arr)
else:
for i in range(1, n+1):
if visited[i] == True:
continue
else:
arr[level] = i
visited[i] = True
permutation(level+1)
visited[i] = False
n, m = map(int,sys.stdin.readline().rstrip().split())
visited = [False] * (n+1)
arr = [0] * m
res = []
permutation(0)
for i in res:
print(' '.join(map(str,i)))- 두 번째 방법
- res.append(arr) 로 arr 자체를 삽입하지 않고 res.append(arr.copy()) 를 이용해서 값을 삽입
import sys
def permutation(level):
if level >= m:
res.append(arr.copy())
else:
for i in range(1, n+1):
if visited[i] == True:
continue
else:
arr[level] = i
visited[i] = True
permutation(level+1)
visited[i] = False
n, m = map(int,sys.stdin.readline().rstrip().split())
visited = [False] * (n+1)
arr = [0] * m
res = []
permutation(0)
for i in res:
print(' '.join(map(str,i)))
3. Others' Solutions
4. Learned
- 파이썬에서 리스트의 각 요소(list[index])는 기본 데이터 타입을 제외하고는 값을 저장하는 것이 아니라 값(객체)을 참조(가르킴)하고 있음
- 값을 저장하기 위해서는 .copy() 함수를 이용하여 새로운 객체? 를 만든다음 그 객체를 참조
