rofem

www.acmicpc.net/problem/1168

1158번 요세푸스 문제와 달리 세그먼트 트리를 구현해야만 통과가 가능하다.

푸는데는 성공했지만 내 역량 밖이라 더 공부하고 다시 풀어야 할 것 같다.

코드는 내가 완전히 익히면 공개해야겠다.

아래는 문제풀 때 참고했던 글들 >>>

1. 세그먼트 트리 정리

www.crocus.co.kr/648

2. c++로 구현 한 분들

cocoon1787.tistory.com/433

suri78.tistory.com/274

www.acmicpc.net/problem/1107

리모컨을 부수고 싶었던 문제다ㅠ

풀이

1. 완전 탐색
2. +- 다 가능하므로 범위는 1000000까지
3. 초기 값인 100에서 목표 값 까지 모든 버튼이 고장난 경우를 생각하여 최소 값을 목표 값 - 100으로 지정 해준다
4. -> 이걸로 목표가 100일 때 예외 처리도 가능

주의점
- 고장난 리모컨이 없을 경우엔 고장난 버튼 입력을 받지 않아야 하므로 if문으로 예외 처리 해주기

import sys
input = sys.stdin.readline

num = int(input())
M = int(input())

array = [0 for _ in range(10)]
flag = True
if M != 0 :
    button = list(map(int, input().split()))
    for i in button:
        array[i] = 1

cnt = abs(num-100)

for i in range(1000001):
    list_i = list(str(i))
    flag = False
    for j in list_i:
        if array[int(j)]==0 : continue
        else:
            flag = True
            break

    if not flag:
        tmp = abs(num-i) + len(list_i)
        if cnt > tmp:
            cnt = tmp
print(cnt)

www.acmicpc.net/problem/1967

1. 루트로부터 가중치를 구한다.

2. 가중치 값이 들어있는 result 배열에서 최대 값 찾기

3. 최대 값을 가진 노드로부터 각 노드까지의 거리(지름)을 구하여 result 배열에 넣는다.

4. 그 배열에서 가장 큰 값이 최장 지름!

 주의점
- 루트에서 루트, index에서 index일때는 0으로 초기화 시켜준다. 

import sys
from collections import deque
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 9)

N = int(input())
graph = [[] for _ in range(N+1)]
result = [0 for _ in range(N+1)]

max = 0

for i in range(N-1):
    a,b,c = map(int, input().split())
    graph[a].append([b,c])
    graph[b].append([a,c])

def bfs(i, graph, result):
    q = deque()
    for j in range(len(graph[i])):
        q.append(graph[i][j])
    while q:
        a,b = q.popleft()
        if result[a] == 0:
            result[a] = result[i] + b
            bfs(a, graph, result)

bfs(1, graph, result)
result[1] = 0

index = 0
tmp_max = 0
for i in range(len(result)):
    if tmp_max < result[i]:
        tmp_max = result[i]
        index = i

result = [0 for _ in range(N+1)]
bfs(index, graph, result)
result[index] = 0

tmp_max = 0
for i in range(len(result)):
    if tmp_max < result[i]:
        tmp_max = result[i]

print(tmp_max)