https://www.acmicpc.net/problem/1789

 

1789번: 수들의 합

첫째 줄에 자연수 S(1 ≤ S ≤ 4,294,967,295)가 주어진다.

www.acmicpc.net

문제 해결을 위한 과정

이 문제의 경우 난이도에 비해 생각을 하기가 조금 어려웠던 문제였습니다. 1부터 하나씩 더해가면서 만든 합이 S를 초과하는 순간 1부터 하니씩 더한 숫자들의 개수 - 1이 자연수 N의 최댓값 입니다.

이를 적용하면 다음과 같습니다. 

1 + 2 + 3 + 4 .... + 17 + 18 + 19 + 20 = 210 

즉 20을 더했을때 S를 초과하므로 20까지의 숫자들의 개수(20개) - 1 즉 19 입니다.

소스코드
1
2
3
4
5
6
7
8
9
10
11
12
n = int(input())
 
count = 0
ans = 0
for i in range(1, n):
  ans += i
  count += 1
  if ans > n:
    count -= 1
    break
 
print(count)
 cs

'알고리즘 > 백준' 카테고리의 다른 글

백준 알고리즘 1946번: 신입 사원(Python)  (0) 2022.01.06
백준 알고리즘 11866번: 요세푸스 문(Python)  (0) 2022.01.06
백준 알고리즘 10610번: 30(Python)  (0) 2022.01.03
백준 알고리즘 1026: 보물(Python)  (0) 2022.01.03
백준 알고리즘 1010번: 다리 놓기 (Python)  (0) 2021.12.27

https://www.acmicpc.net/problem/10610

 

10610번: 30

어느 날, 미르코는 우연히 길거리에서 양수 N을 보았다. 미르코는 30이란 수를 존경하기 때문에, 그는 길거리에서 찾은 수에 포함된 숫자들을 섞어 30의 배수가 되는 가장 큰 수를 만들고 싶어한

www.acmicpc.net

문제 해결을 위한 과정

이 문제는 그리디 알고리즘으로 그다지 어렵지 않은 문제였습니다. 30의 배수가 되려면 10의 배수이면서 3의 배수여야 합니다. 따라서 내림차순으로 정렬을 하였을 때 일의 자릿수가 0이면서 3의 배수이어야 합니다. 

문제 해결을 위한 팁

저의 경우 내림차순으로 정렬을 하기 위해 각각의 숫자를 str로 입력받은 후 내림차순으로 정렬한 후 int로 변경하였습니다.

소스코드
1
2
3
4
5
6
7
8
9
10
11
12
13
s = list(map(str, input()))
s.sort(reverse = True)
 
temp = ""
for i in range(len(s)):
  temp += s[i]
 
temp = int(temp)
 
if temp % 10 != 0 or temp % 3 != 0:
  print(-1)
else:
  print(temp)
 cs

 

'알고리즘 > 백준' 카테고리의 다른 글

백준 알고리즘 11866번: 요세푸스 문(Python)  (0) 2022.01.06
백준 알고리즘 1789번: 수들의 합 (Python)  (0) 2022.01.03
백준 알고리즘 1026: 보물(Python)  (0) 2022.01.03
백준 알고리즘 1010번: 다리 놓기 (Python)  (0) 2021.12.27
백준 알고리즘 1463번: 1로 만들기 (Python)  (0) 2021.12.27

https://www.acmicpc.net/problem/1026

 

1026번: 보물

첫째 줄에 N이 주어진다. 둘째 줄에는 A에 있는 N개의 수가 순서대로 주어지고, 셋째 줄에는 B에 있는 수가 순서대로 주어진다. N은 50보다 작거나 같은 자연수이고, A와 B의 각 원소는 100보다 작거

www.acmicpc.net

문제 해결을 위한 과정

이 문제는 단순한 그리디 알고리즘 문제입니다. 각각의 배열의 원소들을 곱한 후 합을 의미하는 S가 가장 작으려면

a 리스트의 가장 작은 값과 b 리스트의 가장 큰 값을 곱한 후 각각의 배열의 원소들을 곱한 후 합하면 됩니다.

소스코드
1
2
3
4
5
6
7
8
9
10
11
12
n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
 
a.sort()
b.sort(reverse = True)
 
sum = 0
for i in range(n):
  sum += (a[i] * b[i])
 
print(sum)
 cs

 

'알고리즘 > 백준' 카테고리의 다른 글

백준 알고리즘 1789번: 수들의 합 (Python)  (0) 2022.01.03
백준 알고리즘 10610번: 30(Python)  (0) 2022.01.03
백준 알고리즘 1010번: 다리 놓기 (Python)  (0) 2021.12.27
백준 알고리즘 1463번: 1로 만들기 (Python)  (0) 2021.12.27
백준 알고리즘 13549: 숨바꼭질 3(Python)  (0) 2021.02.25

https://www.acmicpc.net/problem/1010

 

1010번: 다리 놓기

입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트케이스에 대해 강의 서쪽과 동쪽에 있는 사이트의 개수 정수 N, M (0 < N ≤ M < 30)이 주어진다.

www.acmicpc.net

문제 해결을 위한 과정

이 문제는 순서를 중요하게 생각하지 않는 '조합'의 방식으로 해결할 수 있는 문제였습니다. 동시에 팩토리얼 연산을 해야 하므로 Dynamic Programming의 방식 역시 문제 풀이의 한 요소였습니다.

팩토리얼을 우리가 흔히 아는 방식 즉 재귀적으로 구현하게 되면 한번 구한 연산을 지속적으로 반복하기 때문에 필요 없는 수많은 연산을 하게 되어 많은 컴퓨팅 리소스를 잡아먹게 됩니다. 또한 당연하게도 시간제한에 걸리게 됩니다. 따라서 이를 시간 내에 구현할 수 있게 하기 위해 피보나치수열 혹은 팩토리얼의 경우 탑다운 또는 보텀업 방식을 이용하여 해결합니다. 

문제에서 N <= M이라는 조건으로 생각해보면 결국 M개의 사이트 중에서 순서에 상관없이 N개를 뽑는 경우입니다. 가령 N이 2개이고 M이 3개일 시, 3개의 M 중에서 2개를 순서에 상관없이 뽑는 경우입니다. (예를 들면 AB, AC, BA, BC, CA, CB) 이를 염두에 두고 소스코드를 작성하면 다음과 같습니다.

소스코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
dp = [0] * 31
dp[0] = 1
dp[1] = 1
 
for i in range(2, 31):
  dp[i] = dp[i-1] * i
 
T = int(input())
for i in range(T):
  n, m = map(int, input().split())
  a = dp[m-n]
  b = dp[m]
  c = dp[n]
 
  print((b//a)//c)
 cs

위 소스코드에서 b//a는 mPn이고 이 결과를 c로 나눠야 mCn입니다.

'알고리즘 > 백준' 카테고리의 다른 글

백준 알고리즘 10610번: 30(Python)  (0) 2022.01.03
백준 알고리즘 1026: 보물(Python)  (0) 2022.01.03
백준 알고리즘 1463번: 1로 만들기 (Python)  (0) 2021.12.27
백준 알고리즘 13549: 숨바꼭질 3(Python)  (0) 2021.02.25
백준 알고리즘 1504: 특정한 최단 경로(Python)  (0) 2021.02.23

https://www.acmicpc.net/problem/1463

 

1463번: 1로 만들기

첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다.

www.acmicpc.net

문제 해결을 위한 과정

이 문제의 경우 전형적인 Dynamic programming 방식으로 풀 수 있는 문제입니다. 풀이 역시 정형화되어있기 때문에 쉽게 해결할 수 있습니다. 

문제에서 정수 X에 사용할 수 있는 연산은 다음과 같이 3가지라고 합니다.

 

1. X가 3으로 나누어 떨어지면, 3으로 나눈다.

2. X가 2로 나누어 떨어지면, 2로 나눈다.

3. 1을 뺀다.

즉 이 문제는 먼저 문제에서 주어진 대로 10^6크기의 dp라는 리스트를 만든 후 INF로 초기화해줍니다. 그 후 dp[0], dp[1]은 0으로 재정의 해줍니다. (1로 만드는 것이므로 1은 이미 1이기 때문에 0번의 연산이 필요하므로) 그 후 반복문으로 차근차근 조회해나가면서 1을 빼는 방법, 2를 나누는 방법, 3을 나누는 방법의 필요한 최솟값을 구해주면 됩니다. 

예시에서 보여준 10의 경우를 살펴보겠습니다. 즉 필요한 식은 다음과 같습니다.

min(dp[i-1]+1, dp[i//2]+1, dp[i//3]+1)

소스코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
n = int(input())
INF = int(1e9)
 
dp = [INF] * (1+n)
dp[0] = 0
dp[1] = 0
 
for i in range(2, n+1):
  dp[i] = dp[i-1] + 1
  if i % 2 == 0:
    dp[i] = min(dp[i], dp[i//2] + 1)
  if i % 3 == 0:
    dp[i] = min(dp[i], dp[i//3] + 1)
 
print(dp[n])
 cs

 

'알고리즘 > 백준' 카테고리의 다른 글

백준 알고리즘 1026: 보물(Python)  (0) 2022.01.03
백준 알고리즘 1010번: 다리 놓기 (Python)  (0) 2021.12.27
백준 알고리즘 13549: 숨바꼭질 3(Python)  (0) 2021.02.25
백준 알고리즘 1504: 특정한 최단 경로(Python)  (0) 2021.02.23
백준 알고리즘 1068: 트리(Python)  (0) 2021.02.21

www.acmicpc.net/problem/13549

 

13549번: 숨바꼭질 3

수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일

www.acmicpc.net

 

문제 해결을 위한 과정

이 문제의 경우 BFS를 이용하면 해결할 수 있는 문제였습니다. 보통 BFS 문제의 경우 이차원 리스트 혹은 이차원 배열에서 특정 지점에서 다른 지점으로 퍼져나가는 형식으로 탐색하는 것인데 특이하게 이 문제의 경우 일차원 리스트상에서 해결해야 하기 때문에 처음에는 생각하기가 조금 어려웠던 문제였습니다.

먼저 문제의 예시를 살펴보도록 하겠습니다.

5의 위치에서 시작하여 17까지 가야합니다. 시간이 걸리지 않는 순간이동의 방식으로 현재 위치 * 2 한 지점으로 이동할 수 있습니다. 또는 시간이 1초 걸려서 현재 위치의 좌측 위치 혹은 우측 위치로 이동할 수 있습니다.

이를 너비 우선이 방식으로 큐에 넣어주고 차례 차례 탐색해 나갑니다.

소스코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
n, m = map(int, input().split())
max = 100001
visited = [0] * max
move = [-1, 1]
 
def bfs():
    q = deque()
    q.append(n)
    count = 0
    visited[n] = 1
    if 2*n < max and not visited[2*n]: # 범위를 벗어나지 않으면서 방문하지 않은 지역인 경우 순간이동으로 탐색
        visited[2*n] = 1
        q.append(2*n)
    if visited[m] != 0: # 도착점인 경우 
        print(visited[m] - 1)
        return
    while q:
        pos = q.popleft()
        if visited[m] != 0: # 도착점인 경우
            print(visited[m] - 1)
            return
        if 2*pos < max and not visited[2*pos]: # 범위를 벗어나지 않으면서 방문하지 않은 지역인 경우
            visited[2*pos] = visited[pos] # 순간이동으로 탐색
            q.append(2*pos)
        for i in range(2): # 시간을 1초 소비하며 좌, 우를 탐색하는 경우
           npos = pos + move[i]
           if 0 <= npos < max:
               if not visited[npos]:
                   visited[npos] = visited[pos] + 1
                   q.append(npos)
 
bfs()
 
 cs

 

'알고리즘 > 백준' 카테고리의 다른 글

백준 알고리즘 1010번: 다리 놓기 (Python)  (0) 2021.12.27
백준 알고리즘 1463번: 1로 만들기 (Python)  (0) 2021.12.27
백준 알고리즘 1504: 특정한 최단 경로(Python)  (0) 2021.02.23
백준 알고리즘 1068: 트리(Python)  (0) 2021.02.21
백준 알고리즘 1074: Z(Python)  (0) 2021.02.20

www.acmicpc.net/problem/1504

 

1504번: 특정한 최단 경로

첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존

www.acmicpc.net

문제 해결을 위한 과정

이 문제의 경우 다익스트라 알고리즘을 이용하면 쉽게 해결할 수 있는 문제였습니다. 그러나 주의할 점이 있었는데 바로 꼭 거쳐야하는 2개의 지점이 있다는것 입니다. 지나가야 하는 지점이 x, y라 할 경우

1 -> x -> y -> N

1 -> y -> x -> N 

이렇게 두가지의 경우가 있으므로 위의 두가지 경우에 대한 다익스트라 알고리즘을 적용하여 거리를 각각 구한 후 더 작은 숫자를 출력하면 됩니다. 또한 문제에서 이동할 수 없는 거리라면 -1을 출력하라는 조건이 있었기 때문에 이를 유의하여 해결합니다.

소스코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
import heapq
INF = 1001
 
n, m = map(int, input().split())
graph = [[] for _ in range(1 + n)]
 
for i in range(m):
    a, b, c = map(int, input().split())
    graph[a].append((b, c))
    graph[b].append((a, c))
 
def dijkstra(start, pos):
    distance = [INF] * (1 + n)
    q = []
    heapq.heappush(q, (0, start))
    distance[start] = 0
    while q:
        dist, now = heapq.heappop(q)
        if distance[now] < dist:
            continue
        for i in graph[now]:
            cost = dist + i[1]
            if cost < distance[i[0]]:
                distance[i[0]] = cost
                heapq.heappush(q, (cost, i[0]))
       
    return distance[pos]
x, y = map(int, input().split())
dist1 = dijkstra(1, x)
dist2 = dijkstra(x, y)
dist3 = dijkstra(y, n)
 
dist4 = dijkstra(1, y)
dist5 = dijkstra(y, x)
dist6 = dijkstra(x, n)
 
ans = min(dist1 + dist2 + dist3, dist4 + dist5 + dist6)
if ans >= INF:
    print(-1)
else:
    print(ans)
 
 
cs

 

'알고리즘 > 백준' 카테고리의 다른 글

백준 알고리즘 1463번: 1로 만들기 (Python)  (0) 2021.12.27
백준 알고리즘 13549: 숨바꼭질 3(Python)  (0) 2021.02.25
백준 알고리즘 1068: 트리(Python)  (0) 2021.02.21
백준 알고리즘 1074: Z(Python)  (0) 2021.02.20
백준 알고리즘 13459: 구슬 탈출(Python)  (0) 2021.02.19

www.acmicpc.net/problem/1068

 

1068번: 트리

첫째 줄에 트리의 노드의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 0번 노드부터 N-1번 노드까지, 각 노드의 부모가 주어진다. 만약 부모가 없다면 (루트) -1이 주어진다

www.acmicpc.net

문제 해결을 위한 과정

이 문제의 경우 DFS 카테고리에 있었던 깊이 우선 탐색 방식으로 해결할 수 있었던 문제입니다. 저는 처음에 tree구조를 직접 정의하여 해결하려 했으나 복잡하게 해결하는 것 같아 트리를 구현하는 방식이 아닌 단순하게 리스트에 그래프를 삽입하고 dfs를 이용하여 해결하는 기본적인 방식으로 해결하였습니다. 

문제의 예제 2번을 기준으로 설명드리겠습니다. -1 0 0 1 1 인데 0번째 노드는 root노드이므로 따로 빼두고 나머지 경우를 보겠습니다. 그 후 노드 1을 제거합니다. 그 과정은 다음 그림과 같습니다.

좌측은 1을 제거하기전 우측은 1을 제거한 후입니다. 리프 노드가 3개에서 1개로 감소한 것을 알 수 있습니다.

따라서 문제에서 주어진 노드부터 차례차례 삭제를 해 나아간 후(dfs를 응용한 remove함수로 구현) dfs를 이용해 리프 노드의 개수를 세주면 됩니다.

문제 해결을 위한 과정

위의 과정에 단 한가지 예외가 붙는데 바로 루트 노드를 삭제하는 경우입니다. 처음 입력받을 때 루트 노드를 따로 뺀 후 삭제를 시작할 입력받은 노드가 루트 노드라면 바로 0을 출력해주면 됩니다. 이유는 루트 노드를 삭제하는 경우 전체 노드가 없어지기 때문입니다.

소스코드 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
import copy
n = int(input())
graph = [[] for _ in range(n+1)]
data = list(map(int, input().split()))
for i in range(n):
    if data[i] == -1: # 부모가 -1인 경우 루트노드로 설정
        root = i
        continue
    graph[data[i]].append(i) # 루트노드가 아닌경우 해당 그래프의 점에 연결
start = int(input())
 
def dfs(graph, visited, v): # dfs 방식으로 탐색
    global count
    visited[v] = True # 방문처리
    if len(graph[v]) == 0: # 리프 노드의 개수를 셈
        count += 1
    for i in graph[v]: # 방문처리하지 않은 노드를 재귀의 방식으로 dfs 탐색
        if not visited[i]:
            dfs(graph, visited, i)
    return count
 
def remove(tempgraph, graph, visited, v): # 입력받은 수의 자식노드를 제거해나가는 함수 dfs 방식 응용
    visited[v] = True
    for i in range(n): # 그래프를 조회하며 dfs 방식으로 탐색한 노드들을 tempgraph에서 삭제
        for j in range(len(graph[i])):
            if graph[i][j] == v:
                tempgraph[i].remove(v)
    for i in graph[v]:
        if not visited[i]:
            remove(tempgraph, graph, visited, i)
 
if start != root: # 지우기 시작할 노드가 root가 아닌경우
    tempgraph = copy.deepcopy(graph) # graph를 복사하여 tempgraph생성
    count = 0
    visited = [0] * (1 + n)
    remove(tempgraph, graph, visited, start)
 
    count = 0
    visited = [0] * (1 + n)
    print(dfs(tempgraph, visited, root))
else: # 지우기 시작할 노드가 root인 경우 그냥 0을 출력함
    print(0)
 cs

 

'알고리즘 > 백준' 카테고리의 다른 글

백준 알고리즘 13549: 숨바꼭질 3(Python)  (0) 2021.02.25
백준 알고리즘 1504: 특정한 최단 경로(Python)  (0) 2021.02.23
백준 알고리즘 1074: Z(Python)  (0) 2021.02.20
백준 알고리즘 13459: 구슬 탈출(Python)  (0) 2021.02.19
백준 알고리즘 13460: 구슬 탈출 2 (Python)  (1) 2021.02.19

+ Recent posts

티스토리툴바