졍's 기술 블로그

Hello World

티어 : Bronze 5
시간 제한 : 1 초
메모리 제한 : 128 MB
알고리즘 분류 : 구현

문제

Hello World!를 출력하시오.

입력

없음

출력

Hello World!를 출력하시오.

예제 입출력

Code

print('Hello World!')

메모리: 29200 KB
시간: 64 ms

별 찍기 - 1

티어 : Bronze 3
시간 제한 : 1 초
메모리 제한 : 128 MB
알고리즘 분류 : 구현

문제

첫째 줄에는 별 1개, 둘째 줄에는 별 2개, N번째 줄에는 별 N개를 찍는 문제

입력

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

출력

첫째 줄부터 N번째 줄까지 차례대로 별을 출력한다.

예제 입출력

Code

for i in range(1, int(input())+1):
    print('*'*i)

메모리: 30840 KB
시간: 68 ms

분해합

티어 : Bronze 2
시간 제한 : 2 초
메모리 제한 : 192 MB
알고리즘 분류 : 브루트포스 알고리즘

문제

어떤 자연수 N이 있을 때, 그 자연수 N의 분해합은 N과 N을 이루는 각 자리수의 합을 의미한다. 어떤 자연수 M의 분해합이 N인 경우, M을 N의 생성자라 한다. 예를 들어, 245의 분해합은 256(=245+2+4+5)이 된다. 따라서 245는 256의 생성자가 된다. 물론, 어떤 자연수의 경우에는 생성자가 없을 수도 있다. 반대로, 생성자가 여러 개인 자연수도 있을 수 있다.

자연수 N이 주어졌을 때, N의 가장 작은 생성자를 구해내는 프로그램을 작성하시오.

입력

첫째 줄에 자연수 N(1 ≤ N ≤ 1,000,000)이 주어진다.

출력

첫째 줄에 답을 출력한다. 생성자가 없는 경우에는 0을 출력한다.

예제 입출력

Code

N = int(input()) # 분해합

# 분해합부터 작아지면서 생성자와 생성자의 각 자리수의 합이 분해합을 만족하는지 확인
min_ = 0
for i in range(N-1, -1, -1):
    temp = str(i) # i를 str형으로 변경
    nums = []
    # 숫자의 각 자리수를 리스트 형태로 저장
    for j in range(len(temp)):
        nums.append(int(temp[j]))
    # 숫자의 각 자리수와 해당 숫자를 더했을 때 N이 나온다면 최솟값 갱신
    if sum(nums) + i == N:
        min_ = i
        
print(min_)

메모리: 30864 KB
시간: 2444 ms

벌집

티어 : Bronze 2
시간 제한 : 2 초
메모리 제한 : 128 MB
알고리즘 분류 : 수학

문제

위의 그림과 같이 육각형으로 이루어진 벌집이 있다. 그림에서 보는 바와 같이 중앙의 방 1부터 시작해서 이웃하는 방에 돌아가면서 1씩 증가하는 번호를 주소로 매길 수 있다. 숫자 N이 주어졌을 때, 벌집의 중앙 1에서 N번 방까지 최소 개수의 방을 지나서 갈 때 몇 개의 방을 지나가는지(시작과 끝을 포함하여)를 계산하는 프로그램을 작성하시오. 예를 들면, 13까지는 3개, 58까지는 5개를 지난다.

입력

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

출력

입력으로 주어진 방까지 최소 개수의 방을 지나서 갈 때 몇 개의 방을 지나는지 출력한다.

예제 입출력

Code

N = int(input())

cum_sum = 1
count = 1
if N == 1:
    print(count)
else:
    while True:
        cum_sum += 6 * count
        count += 1
        if cum_sum >= N:
            print(count)
            break

메모리: 30864 KB
시간: 72 ms

스타트와 링크

티어 : 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