구름톤 챌린지 2주차

문자열 나누기

n = int(input())
st = input()
# 최적화된 코드

# 모든 부분 문자열 찾기 (중복 제외, 길이가 n-2 이하인 부분 문자열만 포함)
all_substrings = set()
for i in range(n):
  for j in range(i + 1, n + 1):
    if len(st[i:j]) > n - 2:
      continue
    all_substrings.add(st[i:j])
all_substrings = sorted(list(all_substrings))

# 부분 문자열 인덱스 캐싱
substring_index_mapping = {substring: idx for idx, substring in enumerate(all_substrings)}

# 최대 점수를 저장할 변수 초기화
max_score = 0

# 첫 번째 분할 지점을 설정
for first_split in range(1, n - 1):  # n-1까지 가능
  # 두 번째 분할 지점을 설정
  for second_split in range(first_split + 1, n):  # n까지 가능
    # 세 부분 문자열로 나누기
    part1 = st[:first_split]
    part2 = st[first_split:second_split]
    part3 = st[second_split:]

    # 각 부분 문자열의 점수 계산
    score_part1 = substring_index_mapping[part1] + 1
    score_part2 = substring_index_mapping[part2] + 1
    score_part3 = substring_index_mapping[part3] + 1

    # 총 점수 계산
    total_score = score_part1 + score_part2 + score_part3

    # 최대 점수 업데이트
    max_score = max(max_score, total_score)

print(max_score)

모든 부분 문자열을 찾는다. 부분 문자열의 특징은 중복이 없고, 연속적이며 길이가 1이상 n-2이하인 문자열이다

문자열을 3토막 내기 때문에, O(n^2)의 시간 복잡도로 문자열을 쪼갤 수 있다
이 후 반복적으로 최댓 값을 계산하면 된다

구름 찾기 깃발

N,K = map(int,input().split())

mp = [list(map(int,input().split())) for _ in range(N)]

m = [[0 for _ in range(N)] for _ in range(N)]

def check(x, y):
	global m
	for i in range(x-1,x+2,1):
		for j in range(y-1,y+2,1):
			if i<0 or j<0 or i==N or j==N:
				continue	
			if mp[i][j]==1:
				continue
			m[i][j]+=1
			
			
for i in range(N):
	for j in range(N):
		if mp[i][j]==1:
			check(i,j)
answer= 0
for i in range(N):
	for j in range(N):
		if m[i][j]==K:
			answer+=1

print(answer)

시간 초과 뜰 줄 알았는데 다행이 통과 했다. 구현 로직 자체는 간단하다

문제도 위의 그림과

내가 생각 한건,깃발을 저장한 지도와 별개로 하나의 맵을 만들어서 체크를 하는거다
구름 주위로 구름이 아니며, 맵 안에 있는 8방면에 대해서 1씩 더한다

최종적으로 K와 동일한 블록을 찾으면 끝!

통증

N= int(input())
cnt = 0
for x in [14,7,1]:
	if N%x==N:
		continue
	cnt+=N//x
	N%=x
print(cnt)

처음엔 while 문 돌려서 구현했더니, 시간 초과가 발생해서, 좀 더 단순하게 바꿨다
나머지가 계산 전후로 동일하다면 자신보다 큰 수 이므로 넘어가게 하는건데, 이렇게 하면 무조건 0이하로 통증 수치가 내려갈 일이 없다
일거양득!