5주차
문제풀이
2468번: 안전 영역
재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는
www.acmicpc.net
from collections import deque
n = int(input())
array = []
for i in range(n):
array.append(list(map(int,input().split())))
dx = [-1,0,1,0]
dy = [0,1,0,-1]
q = deque()
def BFS(number):
while q:
x,y = q.popleft()
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if 0<=nx<n and 0<=ny<n:
if array[nx][ny] >= number and visit[nx][ny] == False:
q.append((nx,ny))
visit[nx][ny] = True
count = 0
for num in range(1,101):
visit = [[False for _ in range(n)] for _ in range(n)]
now_count = 0
for i in range(n):
for j in range(n):
if array[i][j] >= num and visit[i][j] == False:
visit[i][j] = True
q.append((i,j))
BFS(num)
now_count += 1
count = max(count,now_count)
print(count)이 문제는 기존에 했었던 BFS를 높이를 1부터 100까지 설정하고 돌리면 된다. ( 100번 )
매번 돌릴때마다 visit 배열을 선언해주고 특정 높이 이상이면 방문을 하는 형식으로 돌리면 쉽게 풀 수 있다. 그리고 매 높이마다 count (현재까지 나온 최다 구역) 와 now_count(현재 높이의 구역) 을 비교해서 max값을 다시 count에 저장해준다.
6603번: 로또
입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있다. 첫 번째 수는 k (6 < k < 13)이고, 다음 k개 수는 집합 S에 포함되는 수이다. S의 원소는 오름차순으로
www.acmicpc.net
from itertools import combinations
while(True):
array = list(map(int,input().split()))
if array[0] == 0:
break
t = array[0]
del array[0]
todo = list(combinations(array,6))
for i in range(len(todo)):
print(*todo[i])
print()combinations 라이브러리를 이용해서 활용하면 되는 쉬운 문제이다. 물론 이 라이브러리를 사용해 본 적이 없다면 이 문제가 좋은 예제가 될 수 있다. 배열앞에 *를 붙여서 출력할 경우 배열 안에 있는 원소가 한칸씩 띄워져서 출력된다.
11048번: 이동하기
준규는 N×M 크기의 미로에 갇혀있다. 미로는 1×1크기의 방으로 나누어져 있고, 각 방에는 사탕이 놓여져 있다. 미로의 가장 왼쪽 윗 방은 (1, 1)이고, 가장 오른쪽 아랫 방은 (N, M)이다. 준규는
www.acmicpc.net
n , m = map(int,input().split())
array = []
for _ in range(n):
array.append(list(map(int,input().split())))
dp = [[0 for i in range(m)] for i in range(n)]
dp[0][0] = array[0][0]
for i in range(1,m):
dp[0][i] = array[0][i] + dp[0][i-1]
for i in range(1,n):
dp[i][0] = array[i][0] + dp[i-1][0]
for i in range(1,n):
for j in range(1,m):
dp[i][j] = array[i][j] + max(dp[i-1][j],dp[i][j-1])
print(dp[n-1][m-1])dp를 이용하는 문제이고 동, 남 방향으로만 이동하는 것을 인지하고 시작하면 쉽게 풀 수 있다. 우선 인덱스가 0인 row와 column을 먼저 세팅해주고, (1,1) 부터는 위에서 내려올때랑 왼쪽에서 올 때를 비교해서 큰 값을 저장하는 방식으로 했다.
from collections import deque
import sys
input = sys.stdin.readline
n, m = map(int,input().split())
array = []
for _ in range(n):
array.append(list(map(int,input().split())))
check = [[0 for _ in range(m)] for _ in range(n)]
check[0][0] = array[0][0]
q = deque()
q.append((0,0))
dx = [-1,0,1,0] # 북 동 남 서
dy = [0,1,0,-1] # 북 동 남 서
visit = [[False for _ in range(m)] for _ in range(n)]
while q:
x,y = q.popleft()
for i in range(1,3):
nx = x + dx[i]
ny = y + dy[i]
if 0<=nx<n and 0<=ny<m:
if visit[nx][ny] == False:
q.append((nx,ny))
visit[nx][ny] = True
check[nx][ny] = max(check[nx][ny],check[x][y]+array[nx][ny])
print(check[n-1][m-1])BFS로 푼 방법
코딩테스트 연습 - 전화번호 목록 | 프로그래머스 (programmers.co.kr)
코딩테스트 연습 - 전화번호 목록
전화번호부에 적힌 전화번호 중, 한 번호가 다른 번호의 접두어인 경우가 있는지 확인하려 합니다. 전화번호가 다음과 같을 경우, 구조대 전화번호는 영석이의 전화번호의 접두사입니다. 구조
programmers.co.kr
def solution(phone_book):
answer = True
phone_book.sort()
for i in range(len(phone_book)-1):
t = len(phone_book[i])
if len(phone_book[i+1]) >= t and phone_book[i] in phone_book[i+1][0:t]:
answer = False
return answer
return answer입력으로 들어온 phone_book을 오름차순으로 정렬했을 때 x번째 인덱스와 x+1번째 인덱스에 있는 값이 접두어가 안된다면 x와 x+2는 절대로 접두어가 될 수가 없다. 이 점을 활용해서 문제를 푼다면 for문을 한 번만 돌아도 문제를 해결할 수 있다. if문은 접두어인지 비교하는 문장이다!