그래서 내가 구하고자 하는 수가 몇번째 라인에 있는지, 그 중에서 몇 번째 인덱스에 있는지를 알면 된다.
여기서 end는 그 라인의 마지막 인덱스를 뜻한다. ( 1, 3, 6, 10 ... )
그래서 내가 구하고자 하는 인덱스까지 도달할동안 line과 end를 규칙에 따라 늘려가면 쉽게 찾을 수 있을 것이다.
n = int(input())
line = 0
end = 0
while n > end:
line += 1
end += line
diff = end - n
if line%2 == 0: #짝수 라인 일때
top = line - diff
bottom = diff + 1
else:
top = diff + 1
bottom = line - diff
print("%d/%d"%(top,bottom))
지도 크기 N x M을 입력받은 후에 각각의 좌표 칸 바다(.) 인지 땅(X)인지를 입력한다.
이 때, 50년 후의 섬 주변( 상, 하, 좌, 우) 으로 3개 이상의 바다가 존재한다면 그 땅은 바다로 변하게 된다.
또한 바다만 있는 줄이나 칸은 모두 사라진다. ( 맵의 바깥쪽은 모두 바다이기 때문에 바다만 있는 줄, 칸은 생략된다)
따라서 50년 후에는 당연히 맵의 크기는 줄어들 것이다.
이 때, 50년 후의 지도를 출력하면 된다.
위의 예제로 예를 들면, (3,0)의 X는 위, 왼쪽, 아래가 모두 바다이기 때문에 .으로 변하게 된다.
또한, X=0 ( 첫 번째 줄)은 모두 바다이기 때문에 아예 없애준다.
풀이 과정
이 문제는구현(Implementation)문제이다.
각 칸마다 DFS / BFS 검사를 하듯이 상하좌우로 검사를 해준다. ( 범위를 벗어나면 오류가 나므로 범위 지정은 필수 )
new_graph가 변환 후의 맵인데, deepcopy를 해준 이유는 그냥 복사(=)를 하게 되면 한 맵을 수정하게 되면 두 맵이 같이 바뀌게 된다. 따라서 deepcopy를 해주어 기존 비교용 맵과 새로 바꿀용 맵을 바꾸어 준 것이다.
현재 땅을 기준으로 상하좌우에 바다가 3칸 이상 존재하면 현재 땅을 바다로 만들어 준다.
그리고 첫 번째 X가 나타나는 줄을 start_row, 마지막 X가 나타나는 줄을 end_row로 지정하여
줄여진 맵의 행수를 정해주며
마찬가지로 칸 수도 같은 방식으로 진행하여, 줄여진 맵의 열의 수를 정해준다.
import copy
r, c = map(int, input().split())
graph = []
for i in range(r):
graph.append(list(input()))
new_graph = copy.deepcopy(graph)
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]
for x in range(r):
for y in range(c):
if graph[x][y] == '.':
continue
sea_count = 0
for k in range(4):
nx = x + dx[k]
ny = y + dy[k]
if nx < 0 or nx >= r or ny < 0 or ny >= c:
sea_count += 1
continue
elif graph[nx][ny] == '.':
sea_count += 1
if sea_count >= 3:
new_graph[x][y] = '.'
start_row = 0
start_col = 0
end_row = 0
end_col = 0
min_index = c-1
max_index = 0
for i in range(r):
if 'X' in new_graph[i]:
start_row = i
break
for i in range(r-1, -1, -1):
if 'X' in new_graph[i]:
end_row = i
break
for i in range(start_row, end_row+1):
tmp = [i for i, value in enumerate(new_graph[i]) if value == 'X']
if not tmp:
continue
min_tmp = tmp[0]
max_tmp = tmp[-1]
min_index = min(min_index, min_tmp)
max_index = max(max_index, max_tmp)
for i in range(start_row, end_row+1):
for j in range(min_index, max_index+1):
print(new_graph[i][j], end='')
print()
마지막 쯤에 tmp = [i for i, value in enumerate(new_graph[i]) if value == 'X'] 부분이 헷갈릴 수 있는데,
enumerate는 컬렉션의 원소를 ( 인덱스, 원소값 ) 으로 반환해주는 함수라고 생각하면 된다.
즉 여기서는 (i, value) 형태로 반환하는데 나는 인덱스만 필요하기 때문에 i만 tmp 리스트에 넣으면 된다.
IPv6의 주소는 32자리의 16진수를 4자리씩 끊어 나타낸다. 이때, 각 그룹은 콜론 (:)으로 구분해서 나타낸다.
예를 들면, 2001:0db8:85a3:0000:0000:8a2e:0370:7334 이런 식으로 나타낸다.
문제에서는, 규칙 두가지가 존재한다.
1. 각 그룹의 앞자리의 0의 전체 또는 일부를 생략 할 수 있다. 위의 IPv6을 축약하면, 다음과 같다
2001:db8:85a3:0:00:8a2e:370:7334
2. 만약 0으로만 이루어져 있는 그룹이 있을 경우 그 중 한 개 이상 연속된 그룹을 하나 골라 콜론 2개(::)로 바꿀 수 있다.
2001:db8:85a3::8a2e:370:7334
2번째 규칙은 모호함을 방지하기 위해서 오직 한 번만 사용할 수 있다.
올바른 축약형 IPv6주소가 주어졌을 때, 이를 원래 IPv6 (32자리의 16진수)로 복원하는 프로그램을 작성해야 한다.
예를 들어, 25:09:1985:aa:091:4846:374:bb 라는 입력이 주어졌을 때,
0025:0009:1985:00aa:0091:4846:0374:00bb 이런 식으로 복구하여 출력을 하면 된다.
풀이 과정
1) 입력 문자열을 ":"를 기준으로 나눠 리스트에 담는다. (ip 배열)
2) 각 칸이 4글자이면 복구 전과 후가 같으므로 그대로 옮긴다.
3) 0보다 크고 4글자 보다 작으면 0의 일부만 생략된 것이므로 그 수만큼 0을 추가한다.
4) 0글자이면 경우의 수가 두가지 이다.
4-1) 문제에서 말한 두 번째 규칙인 연속된 그룹들이 생략된 경우
-> 남은 칸 수( 8 - len(ip) ) 들을 모두 0으로 채운다.
4-2) 한 그룹만 생략된 경우
-> 해당 칸만 0으로 모두 채운다.
위의 과정의 소스 코드는 다음과 같다.
ip = list(input().split(":"))
index = 0
ans = ['' for _ in range(8)]
flag = 0
for i in range(len(ip)):
if len(ip[i]) == 4:
ans[index] = ip[i]
index += 1
elif len(ip[i]) > 0:
ans[index] = '0' * (4 - len(ip[i])) + ip[i]
index += 1
else: # len(ip[i]) == 0
if flag == 0:
for j in range(8 - len(ip) + 1):
ans[index] = '0000'
index += 1
flag = 1
else:
ans[index] = '0000'
index += 1
for i in range(len(ans)-1):
print(ans[i], end=':')
print(ans[-1])
높이 h부터 높이 1까지 누적 합을 계산하면 높이 i의 배열 값은 높이 i 이상의 모든 석순의 개수가 된다.
예를 들어, 높이가 6인 동굴에서 높이 5의 개똥벌레가 날아갈 때, 높이 5 이상의 석순에 모두 부딪히기 때문에
배열 5의 값이 높이 5의 개똥벌레가 부딪히는 석순의 개수가 된다.
마찬가지로 종유석은 위에서부터 내려오기 때문에 h - i + 1의 식을 이용하면 된다.
왜냐하면, 높이 6의 동굴에서 높이 2짜리 종유석은 높이 4 (실질적으로 3.5) 위로의 개똥벌레가 모두 부딪히기 때문이다.
즉, 석순처럼 높이2라고 해서 높이 2 밑의 개똥벌레가 부딪히는것이 아니라 위에서 부터기 때문에 반대가 된다.
파이썬 코드는 다음과 같다.
n, h = map(int, input().split())
down = [0] * (h + 1) # 석순
up = [0] * (h + 1) # 종유석
min_count = n # 파괴해야 하는 장애물의 최소값
range_count = 0 # 최소값이 나타나는 구간의 수
for i in range(n):
if i % 2 == 0:
down[int(input())] += 1
else:
up[int(input())] += 1
for i in range(h - 1, 0, -1):
down[i] += down[i + 1]
up[i] += up[i + 1]
for i in range(1, h + 1):
if min_count > (down[i] + up[h - i + 1]):
min_count = (down[i] + up[h - i + 1])
range_count = 1
elif min_count == (down[i] + up[h - i + 1]):
range_count += 1
print(min_count, range_count)
