졍's 기술 블로그

스타트와 링크

티어 : Silver 2
시간 제한 : 2 초
메모리 제한 : 512 MB
알고리즘 분류 : 브루트포스 알고리즘, 백트래킹

문제

오늘은 스타트링크에 다니는 사람들이 모여서 축구를 해보려고 한다. 축구는 평일 오후에 하고 의무 참석도 아니다. 축구를 하기 위해 모인 사람은 총 N명이고 신기하게도 N은 짝수이다. 이제 N/2명으로 이루어진 스타트 팀과 링크 팀으로 사람들을 나눠야 한다.

BOJ를 운영하는 회사 답게 사람에게 번호를 1부터 N까지로 배정했고, 아래와 같은 능력치를 조사했다. 능력치 Sij는 i번 사람과 j번 사람이 같은 팀에 속했을 때, 팀에 더해지는 능력치이다. 팀의 능력치는 팀에 속한 모든 쌍의 능력치 Sij의 합이다. Sij는 Sji와 다를 수도 있으며, i번 사람과 j번 사람이 같은 팀에 속했을 때, 팀에 더해지는 능력치는 Sij와 Sji이다.

N=4이고, S가 아래와 같은 경우를 살펴보자.

예를 들어, 1, 2번이 스타트 팀, 3, 4번이 링크 팀에 속한 경우에 두 팀의 능력치는 아래와 같다.

• 스타트 팀: S12 + S21 = 1 + 4 = 5
• 링크 팀: S34 + S43 = 2 + 5 = 7

1, 3번이 스타트 팀, 2, 4번이 링크 팀에 속하면, 두 팀의 능력치는 아래와 같다.

• 스타트 팀: S13 + S31 = 2 + 7 = 9
• 링크 팀: S24 + S42 = 6 + 4 = 10

축구를 재미있게 하기 위해서 스타트 팀의 능력치와 링크 팀의 능력치의 차이를 최소로 하려고 한다. 위의 예제와 같은 경우에는 1, 4번이 스타트 팀, 2, 3번 팀이 링크 팀에 속하면 스타트 팀의 능력치는 6, 링크 팀의 능력치는 6이 되어서 차이가 0이 되고 이 값이 최소이다.

입력

첫째 줄에 N(4 ≤ N ≤ 20, N은 짝수)이 주어진다. 둘째 줄부터 N개의 줄에 S가 주어진다. 각 줄은 N개의 수로 이루어져 있고, i번 줄의 j번째 수는 Sij 이다. Sii는 항상 0이고, 나머지 Sij는 1보다 크거나 같고, 100보다 작거나 같은 정수이다.

출력

첫째 줄에 스타트 팀과 링크 팀의 능력치의 차이의 최솟값을 출력한다.

예제 입출력

힌트

예제 2의 경우에 (1, 3, 6), (2, 4, 5)로 팀을 나누면 되고, 예제 3의 경우에는 (1, 2, 4, 5), (3, 6, 7, 8)로 팀을 나누면 된다.

Algorithm

back tracking - 재귀
1. start에 사람 번호 추가
2. 재귀함수 호출
3. 재귀함수가 return되면 pop
4. start의 길이가 N//2이면 능력치 구하고 차이 최솟값 갱신

Code

def back_tracking():
    global answer
    
    # start의 길이가 N//2이면 능력치 구하고 차이 최솟값 갱신
    if len(start) == N//2:
        s_start = 0
        s_link = 0
        for num1 in range(N):
            for num2 in range(N):
                if num1 < num2:
                    # 두 명 다 start 팀이면 s_start에 누적합
                    if num1 in start and num2 in start:
                        s_start += S[num1][num2] + S[num2][num1]
                    # 두명 다 start 팀에 없으면 s_link에 누적합
                    elif num1 not in start and num2 not in start:
                        s_link += S[num1][num2] + S[num2][num1]

        # 두 팀이 능력치 차의 최솟값 갱신
        if answer > max(s_start - s_link, s_link - s_start):
            answer = max(s_start - s_link, s_link - s_start)

    else:
        for num in range(N):
            # start 비어있으면 그냥 append
            if not start:
                start.append(num)
                # start[0]이 1이 되면break
                if start[0] == 1:
                    break
                back_tracking()
                start.pop()
            # start 비어있지 않으면 start에 들어있지 않고 start의 마지막 값보다 큰 값만 추가
            elif num not in start and num > start[-1]:
                start.append(num)
                # start[0]이 1이 되면break
                if start[0] == 1:
                    break
                back_tracking()
                start.pop()
                
import sys
input = sys.stdin.readline

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

global answer
answer = 100*N*N
start = []
back_tracking()
print(answer)

메모리: 30864 KB
시간: 7572 ms

퇴사

티어 : Silver 3
시간 제한 : 2 초
메모리 제한 : 512 MB
알고리즘 분류 : 다이나믹 프로그래밍, 브루트포스 알고리즘

문제

상담원으로 일하고 있는 백준이는 퇴사를 하려고 한다.

오늘부터 N+1일째 되는 날 퇴사를 하기 위해서, 남은 N일 동안 최대한 많은 상담을 하려고 한다.

백준이는 비서에게 최대한 많은 상담을 잡으라고 부탁을 했고, 비서는 하루에 하나씩 서로 다른 사람의 상담을 잡아놓았다.

각각의 상담은 상담을 완료하는데 걸리는 기간 Ti와 상담을 했을 때 받을 수 있는 금액 Pi로 이루어져 있다.

N = 7인 경우에 다음과 같은 상담 일정표를 보자.

1일에 잡혀있는 상담은 총 3일이 걸리며, 상담했을 때 받을 수 있는 금액은 10이다. 5일에 잡혀있는 상담은 총 2일이 걸리며, 받을 수 있는 금액은 15이다.

상담을 하는데 필요한 기간은 1일보다 클 수 있기 때문에, 모든 상담을 할 수는 없다. 예를 들어서 1일에 상담을 하게 되면, 2일, 3일에 있는 상담은 할 수 없게 된다. 2일에 있는 상담을 하게 되면, 3, 4, 5, 6일에 잡혀있는 상담은 할 수 없다.

또한, N+1일째에는 회사에 없기 때문에, 6, 7일에 있는 상담을 할 수 없다.

퇴사 전에 할 수 있는 상담의 최대 이익은 1일, 4일, 5일에 있는 상담을 하는 것이며, 이때의 이익은 10+20+15=45이다.

상담을 적절히 했을 때, 백준이가 얻을 수 있는 최대 수익을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N (1 ≤ N ≤ 15)이 주어진다.

둘째 줄부터 N개의 줄에 Ti와 Pi가 공백으로 구분되어서 주어지며, 1일부터 N일까지 순서대로 주어진다. (1 ≤ Ti ≤ 5, 1 ≤ Pi ≤ 1,000)

출력

첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다.

예제 입출력

Algorithm

back tracking - 재귀
1. stack에 상담을 하는 날짜를 추가
1.1. stack이 비어있으면 오늘 날짜 추가
1.2. stack이 비어있지 않으면 T가 0이되는 날짜 추가
2. 재귀함수 호출
    ☞ date를 오늘 날짜 + T로 갱신하고 인자로 전달
3. 재귀함수가 return되면 이익 더하고 pop
4. date가 마지막 값면 수익의 최댓값 갱신

Code

def back_tracking(date):
    global answer
    global sum_
    
    # date가 마지막 값면 수익의 최댓값 갱신
    if date == N:
        if answer < sum_:
            answer = sum_
        date = 0
    else:
        while date < N:
            # stack이 비어있으면
            if not stack:
                # 일이 끝났을 때 N을 넘지 않으면 추가
                if date + info[date][0] <= N:
                    stack.append(date)
                    sum_ += info[date][1]
                    back_tracking(date + info[date][0])
                    stack.pop()
                    sum_ -= info[date][1]

            # stack이 비어있으면 일이 끝났을 때 N을 넘지 않으면 추가
            elif date + info[date][0] <= N:
                    stack.append(date)
                    sum_ += info[date][1]
                    back_tracking(date + info[date][0])
                    stack.pop()
                    sum_ -= info[date][1]
            date += 1
        back_tracking(N)
        

import sys
input = sys.stdin.readline

N = int(input())
info = []
for _ in range(N):
    info.append(list(map(int, input().split())))
stack = []
global answer
global sum_
answer = 0
sum_ = 0
back_tracking(0)
print(answer)

메모리: 30864 KB
시간: 92 ms

암호 만들기

티어 : Gold 5
시간 제한 : 2 초
메모리 제한 : 128 MB
알고리즘 분류 : 수학, 브루트포스 알고리즘, 조합론, 백트래킹

문제

바로 어제 최백준 조교가 방 열쇠를 주머니에 넣은 채 깜빡하고 서울로 가 버리는 황당한 상황에 직면한 조교들은, 702호에 새로운 보안 시스템을 설치하기로 하였다. 이 보안 시스템은 열쇠가 아닌 암호로 동작하게 되어 있는 시스템이다.

암호는 서로 다른 L개의 알파벳 소문자들로 구성되며 최소 한 개의 모음(a, e, i, o, u)과 최소 두 개의 자음으로 구성되어 있다고 알려져 있다. 또한 정렬된 문자열을 선호하는 조교들의 성향으로 미루어 보아 암호를 이루는 알파벳이 암호에서 증가하는 순서로 배열되었을 것이라고 추측된다. 즉, abc는 가능성이 있는 암호이지만 bac는 그렇지 않다.

새 보안 시스템에서 조교들이 암호로 사용했을 법한 문자의 종류는 C가지가 있다고 한다. 이 알파벳을 입수한 민식, 영식 형제는 조교들의 방에 침투하기 위해 암호를 추측해 보려고 한다. C개의 문자들이 모두 주어졌을 때, 가능성 있는 암호들을 모두 구하는 프로그램을 작성하시오.

입력

첫째 줄에 두 정수 L, C가 주어진다. (3 ≤ L ≤ C ≤ 15) 다음 줄에는 C개의 문자들이 공백으로 구분되어 주어진다. 주어지는 문자들은 알파벳 소문자이며, 중복되는 것은 없다.

출력

각 줄에 하나씩, 사전식으로 가능성 있는 암호를 모두 출력한다.

예제 입출력

Algorithm

back tracking - 재귀
1. 입력받은 문자열을 리스트로 저장해 오름차순 정렬
2. stack에 들어있지 않은 문자열 append
3. stack의 길이가 L이 되면 stack 안에 모음이 1개 이상, 자음이 2개 이상 포함되어있는 것만 출력

Code

def back_tracking():
    
    # stack의 길이가 L이 되면
    if len(stack) == L:
        # stack 안에 모음과 자음 개수 확인
        vowel = 0 # 모음
        consonant = 0 # 자음
        for word in stack:
            if word in ['a', 'e', 'i', 'o', 'u']:
                vowel += 1
            else:
                consonant += 1
                
        # stack 안에 모음 1개 이상, 자음 2개 이상 포함되어있으면 출력
        if vowel > 0 and consonant > 1:
            print(''.join(stack))
    else:
        for word in words:
            # stack이 비어있으면
            if not stack:
                # 바로 append
                stack.append(word)
                back_tracking()
                stack.pop()
            # stack 비어있지 않으면 satck에 없고 stack의 마지막 원소보다 큰 알파벳만 저장
            elif word not in stack and word > stack[-1]:
                stack.append(word)
                back_tracking()
                stack.pop()
                
L, C = map(int, input().split())
words = list(input().split())
words.sort()

stack = []
back_tracking()

메모리: 30864 KB
시간: 148 ms

NM과 K (1)

티어 : Silver 1
시간 제한 : 2 초
메모리 제한 : 512 MB
알고리즘 분류 : 브루트포스 알고리즘, 백트래킹

문제

크기가 N×M인 격자판의 각 칸에 정수가 하나씩 들어있다. 이 격자판에서 칸 K개를 선택할 것이고, 선택한 칸에 들어있는 수를 모두 더한 값의 최댓값을 구하려고 한다. 단, 선택한 두 칸이 인접하면 안된다. r행 c열에 있는 칸을 (r, c)라고 했을 때, (r-1, c), (r+1, c), (r, c-1), (r, c+1)에 있는 칸이 인접한 칸이다.

입력

첫째 줄에 N, M, K가 주어진다. 둘째 줄부터 N개의 줄에 격자판에 들어있는 수가 주어진다.

출력

선택한 칸에 들어있는 수를 모두 더한 값의 최댓값을 출력한다.

제한

• 1 ≤ N, M ≤ 10
• 1 ≤ K ≤ min(4, N×M)
• 격자판에 들어있는 수는 -10,000보다 크거나 같고, 10,000보다 작거나 같은 정수이다.
• 항상 K개의 칸을 선택할 수 있는 경우만 입력으로 주어진다.

예제 입출력

Algorithm

back tracking - 재귀 이용
1. graph 구현
2. 2중 for문을 돌면서 인접한 칸이 아니고 visited = False인 칸의 값을 stack에 append
3. append한 칸의 visited 값을 True로 변경하고 재귀함수 호출
4. 재귀함수 return되면 stack에서 pop하고 visited값 False로 변경
5. stack의 길이가 K가 되면 합을 구하고 합의 최댓값으로 갱신

Code

def back_tracking(x, y):
    global answer
    global sum_
    
    # stack의 길이가 K가 되면 합을 구하고 합의 최댓값 갱신
    if len(stack) == K:
        if answer < sum_:
            answer = sum_
    else:
        while x < N:
            while y < M:
                # stack이 비어있으면
                if not stack:
                    # (x, y)의 visited값이 False면 append
                    if not visited[x][y]:
                        stack.append((x, y))
                        visited[x][y] = True
                        sum_ += int(graph[x][y])
                        # 이 때의 x, y값을 인자로 재귀함수 호출
                        back_tracking(x, y)
                        # 재귀함수가 return되면 pop하고 visited False로 변경
                        stack.pop()
                        visited[x][y] = False
                        sum_ -= int(graph[x][y])
                    
                # (x, y)의 visited = False이고 인접한 칸이 아니면 append
                elif not visited[x][y] and (x-1, y) not in stack and (x+1, y) not in stack and (x, y-1) not in stack and (x, y+1) not in stack:
                    stack.append((x, y))
                    visited[x][y] = True
                    sum_ += int(graph[x][y])
                    # 이 때의 x, y값을 인자로 재귀함수 호출
                    back_tracking(x, y)
                    # 재귀함수가 return되면 pop하고 visited False로 변경
                    stack.pop()
                    visited[x][y] = False
                    sum_ -= int(graph[x][y])

                y = y + 1
            x = x + 1
            y = 0

import sys
input = sys.stdin.readline

N, M, K = map(int, input().split())
graph = []
for _ in range(N):
    graph.append(input().rstrip().split())
    
global answer
global sum_
answer = -10000 * K - 1
sum_ = 0
stack = []
visited = [[False for _ in range(M)] for _ in range(N)]
back_tracking(0, 0)
print(answer)

메모리: 30864 KB
시간: 5880 ms

N과 M (8)

티어 : Silver 3
시간 제한 : 1 초
메모리 제한 : 512 MB
알고리즘 분류 : 백트래킹

문제

N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다.

• N개의 자연수 중에서 M개를 고른 수열
• 같은 수를 여러 번 골라도 된다.
• 고른 수열은 비내림차순이어야 한다.
  • 길이가 K인 수열 A가 A1 ≤ A2 ≤ ... ≤ AK-1 ≤ AK를 만족하면, 비내림차순이라고 한다.

입력

첫째 줄에 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)

둘째 줄에 N개의 수가 주어진다. 입력으로 주어지는 수는 10,000보다 작거나 같은 자연수이다.

출력

한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다.

수열은 사전 순으로 증가하는 순서로 출력해야 한다.

예제 입출력

Algorithm

백트래킹 이용
1. 입력 리스트 오름차순 정렬
2. for문을 돌면서 stack 비었는지 확인하며 숫자 append
2.1. stack 비어있으면 바로 append
2.2. stack 비어있지 않으면 num이 stack 마지막 원소보다 크거나 같은 경우에만 append
3. 재귀함수 호출
4. 재귀함수 return되면 pop5. stack의 길이가 M이 되면 print

Code

def back_tracking():
    
    # stack 길이가 M이 되면 print
    if len(stack) == M:
        print(' '.join(list(map(str, stack))))
    else:
        for num in nums:
            # stack 비어있으면 num append
            if not stack:
                stack.append(num)
                back_tracking()
                stack.pop()
            # 그렇지 않으면 stack 마지막 원소보다 크거나 같은 값만 append
            elif stack[-1] <= num:
                stack.append(num)
                back_tracking()
                stack.pop()
                
N, M = map(int, input().split())
nums = list(map(int, input().split()))
nums.sort()

stack = []
back_tracking()

메모리: 30864 KB
시간: 88 ms

N과 M (7)

티어 : Silver 3
시간 제한 : 1 초
메모리 제한 : 512 MB
알고리즘 분류 : 백트래킹

문제

N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다.

• N개의 자연수 중에서 M개를 고른 수열
• 같은 수를 여러 번 골라도 된다.

입력

첫째 줄에 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 7)

둘째 줄에 N개의 수가 주어진다. 입력으로 주어지는 수는 10,000보다 작거나 같은 자연수이다.

출력

한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다.

수열은 사전 순으로 증가하는 순서로 출력해야 한다.

예제 입출력

Algorithm

백트래킹 이용
1. 입력 리스트 오름차순 정렬
2. for문을 돌면서 숫자 append
3. 재귀함수 호출
4. 재귀함수 return되면 pop
5. stack의 길이가 M이 되면 print

Code

def back_tracking():
    
    # stack의 길이가 M이 되면 print
    if len(stack) == M:
        print(' '.join(list(map(str, stack))))
    else:
        # stack에 num 추가
        for num in nums:
            stack.append(num)
            back_tracking()
            stack.pop()

N, M = map(int, input().split())
nums = list(map(int, input().split()))
nums.sort()

stack = []
back_tracking()

메모리: 30864 KB
시간: 1680 ms

N과 M (6)

티어 : Silver 3
시간 제한 : 1 초
메모리 제한 : 512 MB
알고리즘 분류 : 백트래킹

문제

N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다.

• N개의 자연수 중에서 M개를 고른 수열
• 고른 수열은 오름차순이어야 한다.

입력

첫째 줄에 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)

둘째 줄에 N개의 수가 주어진다. 입력으로 주어지는 수는 10,000보다 작거나 같은 자연수이다.

출력

한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다.

수열은 사전 순으로 증가하는 순서로 출력해야 한다.

예제 입출력

Algorithm

백트래킹 이용
1. 입력 리스트 오름차순 정렬
2. for문을 돌면서 stack이 비었는지 확인해 숫자 append
2.1. stack이 비었으면 바로 append
2.2. stack이 안비었으면 stack에 없고 stack 마지막 원소보다 큰 숫자만 append
3. 재귀함수 호출
4. 재귀함수 return되면 pop
5. stack의 길이가 M이 되면 print

Code

def back_tracking():
    
    # stack의 길이가 M이 되면 print
    if len(stack) == M:
        print(' '.join(list(map(str, stack))))
    else:
        for num in nums:
            # stack 비어있으면 숫자 append
            if not stack:
                stack.append(num)
                back_tracking()
                stack.pop()
            # stack에 없고 stack 마지막 원소보다 크면 append
            elif num not in stack and num > stack[-1]:
                stack.append(num)
                back_tracking()
                stack.pop()
                
N, M = map(int, input().split())
nums = list(map(int, input().split()))
nums.sort()
stack = []
back_tracking()

메모리: 30864 KB
시간: 72 ms

N과 M (5)

티어 : Silver 3
시간 제한 : 1 초
메모리 제한 : 512 MB
알고리즘 분류 : 백트래킹

문제

N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다.

• N개의 자연수 중에서 M개를 고른 수열

입력

첫째 줄에 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)

둘째 줄에 N개의 수가 주어진다. 입력으로 주어지는 수는 10,000보다 작거나 같은 자연수이다.

출력

한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다.

수열은 사전 순으로 증가하는 순서로 출력해야 한다.

예제 입출력

Algorithm

back tracking 이용
1. 입력 리스트 오름차순 정렬
2. for문을 돌면서 stack에 없는 숫자 append
3. 재귀함수 호출
4. 재귀함수 return되면 pop
5. stack의 길이가 M이 되면 print

Code

def back_tracking():
    
    # stack의 길이가 M이 되면 print
    if len(stack) == M:
        print(' '.join(list(map(str, stack))))
    else:
        for num in nums:
            # num이 stack에 없으면 append
            if num not in stack:
                stack.append(num)
                back_tracking()
                stack.pop()

N, M = map(int, input().split())
nums = list(map(int, input().split()))

# 입력 수열 오름차순 정렬
nums.sort()
stack = []
back_tracking()

메모리: 30864 KB
시간: 208 ms