반응형

부등호

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

 

문제

두 종류의 부등호 기호 ‘<’와 ‘>’가 k개 나열된 순서열 A가 있다. 우리는 이 부등호 기호 앞뒤에 서로 다른 한 자릿수 숫자를 넣어서 모든 부등호 관계를 만족시키려고 한다. 예를 들어, 제시된 부등호 순서열 A가 다음과 같다고 하자.

A ⇒ < < < > < < > < >

부등호 기호 앞뒤에 넣을 수 있는 숫자는 0부터 9까지의 정수이며 선택된 숫자는 모두 달라야 한다. 아래는 부등호 순서열 A를 만족시키는 한 예이다. 

3 < 4 < 5 < 6 > 1 < 2 < 8 > 7 < 9 > 0

이 상황에서 부등호 기호를 제거한 뒤, 숫자를 모두 붙이면 하나의 수를 만들 수 있는데 이 수를 주어진 부등호 관계를 만족시키는 정수라고 한다. 그런데 주어진 부등호 관계를 만족하는 정수는 하나 이상 존재한다. 예를 들어 3456128790 뿐만 아니라 5689023174도 아래와 같이 부등호 관계 A를 만족시킨다. 

5 < 6 < 8 < 9 > 0 < 2 < 3 > 1 < 7 > 4

여러분은 제시된 k개의 부등호 순서를 만족하는 (k+1)자리의 정수 중에서 최댓값과 최솟값을 찾아야 한다. 앞서 설명한 대로 각 부등호의 앞뒤에 들어가는 숫자는 { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 }중에서 선택해야 하며 선택된 숫자는 모두 달라야 한다

 

입력

첫 줄에 부등호 문자의 개수를 나타내는 정수 k가 주어진다. 그 다음 줄에는 k개의 부등호 기호가 하나의 공백을 두고 한 줄에 모두 제시된다. k의 범위는 2 ≤ k ≤ 9 이다. 

 

출력

여러분은 제시된 부등호 관계를 만족하는 k+1 자리의 최대, 최소 정수를 첫째 줄과 둘째 줄에 각각 출력해야 한다. 단 아래 예(1)과 같이 첫 자리가 0인 경우도 정수에 포함되어야 한다. 모든 입력에 답은 항상 존재하며 출력 정수는 하나의 문자열이 되도록 해야 한다. 

 

예제 입출력


Algorithm

back tracking - 재귀
1. 0부터 9까지 stack에 추가
1.1. stack이 비어있으면 바로 append
1.2. stack이 비어있지 않으면 stack이 없는 값이며 부등호를 확인해 < 이면 stack[-1]보다 큰 값, > 이면 stack[-1]보다 작은 값만 추가
2. 재귀함수 호출
3. 재귀함수 return되면 pop
4. stack의 길이가 K+1이 되면 최댓값, 최솟값 갱신

 

Code

def back_tracking():
    global min_
    global max_

    # stack의 길이가 k+1이 되면
    if len(stack) == k+1:
        num = int(''.join(list(map(str, stack))))
        # 최솟값 갱신
        if min_ > num:
            min_ = num
        # 최댓값 갱신
        if max_ < num:
            max_ = num

    else:
        for i in range(10):
            # stack 비어있으면 바로 추가
            if not stack:
                stack.append(i)
                back_tracking()
                stack.pop()
                
            # stack 비어있지 않으면
            elif i not in stack:
                if inequalities[len(stack)-1] == '<' and stack[-1] < i:
                # stack[-1]보다 큰 값만 추가
                    stack.append(i)
                    back_tracking()
                    stack.pop()
                elif inequalities[len(stack)-1] == '>' and stack[-1] > i:
                # stack[-1]보다 작은 값만 추가
                    stack.append(i)
                    back_tracking()
                    stack.pop()
                
import sys
input = sys.stdin.readline

k = int(input())
inequalities = list(input().rstrip().split())
global min_
global max_
min_ = 9876543211
max_ = 0
stack = []
back_tracking()

answer = ''
for i in range(k+1 - len(str(max_))):
    answer += '0'
answer += str(max_) + '\n'
for i in range(k+1 - len(str(min_))):
    answer += '0'
answer += str(min_)
print(answer)

메모리: 30860 KB
시간: 248 ms

반응형

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

[백준 1931] 회의실 배정 Python  (0) 2022.04.07
[백준 2562] 최댓값 Python  (0) 2022.04.07
[백준 15661] 링크와 스타트 Python  (0) 2022.04.06
[백준 2557] Hello World Python  (0) 2022.04.06
[백준 2438] 별 찍기 - 1 Python  (0) 2022.04.06
반응형

링크와 스타트

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

 

문제

오늘은 스타트링크에 다니는 사람들이 모여서 축구를 해보려고 한다. 축구는 평일 오후에 하고 의무 참석도 아니다. 축구를 하기 위해 모인 사람은 총 N명이다. 이제 스타트 팀과 링크 팀으로 사람들을 나눠야 한다. 두 팀의 인원수는 같지 않아도 되지만, 한 명 이상이어야 한다.

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개의 줄에 S가 주어진다. 각 줄은 N개의 수로 이루어져 있고, i번 줄의 j번째 수는 Sij 이다. Sii는 항상 0이고, 나머지 Sij는 1보다 크거나 같고, 100보다 작거나 같은 정수이다.

 

출력

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

 

예제 입출력


Algorithm

back tracking - 재귀
1. start에 숫자 추가
1.1. start가 비어있으면 그냥 추가
1.2. start가 비어있지 않으면 stack에 들어있지 않고 stack의 마지막 숫자보다 큰 숫자만 추가
2. append될 때마다 두 팀의 능력치 차이에 따라 answer 갱신
3. 재귀함수 호출
4. 재귀함수 return되면 pop
5. start의 길이가 N-1이 되면 append하기 전에 pop부터 하도록 구현

 

Code

import sys
input = sys.stdin.readline

def back_tracking(s_start, s_link):
    global answer
    
    # start 길이가 N - 1이 되면 append하기 전에 pop부터 하도록 구현
    if len(start) == N-1:
        pass
    else:
        for num in range(N):
            # start 비어 있으면 숫자 추가
            if not start:
                # start의 첫 번째 원소가 1이면 return
                if num == 1:
                    return answer
                start.append(num)

                # start에 값이 추가될 때마다 능력치 확인
                for i in start[:-1]:
                    s_start += (S[i][num] + S[num][i])
                for i in range(N):
                    if i not in start:
                        s_link -= (S[num][i] + S[i][num])

                # answer값 갱신
                if answer < max(s_start - s_link, s_link - s_start):
                    answer = max(s_start - s_link, s_link - s_start)

                # 재귀함수 호출하고 return되면 pop
                back_tracking(s_start, s_link)
                
                for i in start[:-1]:
                    s_start -= S[i][start[-1]] + S[start[-1]][i]
                for i in range(N):
                    if i not in start:
                        s_link += (S[num][i] + S[i][num])
                    
                start.pop()
            
            # start 비어있지 않으면 start에 들어있지 않고 start의 마지막 숫자보다 큰 값만 추가
            elif num not in start and start[-1] < num:
                start.append(num)

                for i in start[:-1]:
                    s_start += S[i][num] + S[num][i]
                for i in range(N):
                    if i not in start:
                        s_link -= (S[num][i] + S[i][num])

                # answer값 갱신
                if answer > max(s_start - s_link, s_link - s_start):
                    answer = max(s_start - s_link, s_link - s_start)

                # 재귀함수 호출하고 return되면 pop
                back_tracking(s_start, s_link)

                for i in start[:-1]:
                    s_start -= S[i][num] + S[num][i]
                for i in range(N):
                    if i not in start:
                        s_link += (S[num][i] + S[i][num])
                start.pop()
                
N = int(input())
S = []
temp = []
s_link = 0
for _ in range(N):
    temp = list(map(int, input().split()))
    S.append(temp)
    s_link += sum(temp)

start = []
global answer
answer = 100*N*N
s_start = 0
print(back_tracking(s_start, s_link))

메모리: 30864 KB
시간: 7128 ms

반응형

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

[백준 2562] 최댓값 Python  (0) 2022.04.07
[백준 2529] 부등호 Python  (0) 2022.04.07
[백준 2557] Hello World Python  (0) 2022.04.06
[백준 2438] 별 찍기 - 1 Python  (0) 2022.04.06
[백준 2231] 분해합 Python  (0) 2022.04.06
반응형

분해합

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

반응형

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

[백준 2557] Hello World Python  (0) 2022.04.06
[백준 2438] 별 찍기 - 1 Python  (0) 2022.04.06
[백준 2292] 벌집 Python  (0) 2022.04.06
[백준 14889] 스타트와 링크 Python  (0) 2022.04.06
[백준 14501] 퇴사 Python  (0) 2022.04.06
반응형

스타트와 링크

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

반응형

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

[백준 2231] 분해합 Python  (0) 2022.04.06
[백준 2292] 벌집 Python  (0) 2022.04.06
[백준 14501] 퇴사 Python  (0) 2022.04.06
[백준 1759] 암호 만들기 Python  (0) 2022.04.06
[백준 18290] NM과 K (1) Python  (0) 2022.04.06
반응형

퇴사

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

반응형

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

[백준 2292] 벌집 Python  (0) 2022.04.06
[백준 14889] 스타트와 링크 Python  (0) 2022.04.06
[백준 1759] 암호 만들기 Python  (0) 2022.04.06
[백준 18290] NM과 K (1) Python  (0) 2022.04.06
[백준 15657] N과 M (8) Python  (0) 2022.04.05
반응형

암호 만들기

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

반응형

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

[백준 14889] 스타트와 링크 Python  (0) 2022.04.06
[백준 14501] 퇴사 Python  (0) 2022.04.06
[백준 18290] NM과 K (1) Python  (0) 2022.04.06
[백준 15657] N과 M (8) Python  (0) 2022.04.05
[백준 15656] N과 M (7) Python  (0) 2022.04.05
반응형

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

반응형

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

[백준 14501] 퇴사 Python  (0) 2022.04.06
[백준 1759] 암호 만들기 Python  (0) 2022.04.06
[백준 15657] N과 M (8) Python  (0) 2022.04.05
[백준 15656] N과 M (7) Python  (0) 2022.04.05
[백준 15655] N과 M (6) Python  (0) 2022.04.05
반응형

일곱 난쟁이

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

 

문제

왕비를 피해 일곱 난쟁이들과 함께 평화롭게 생활하고 있던 백설공주에게 위기가 찾아왔다. 일과를 마치고 돌아온 난쟁이가 일곱 명이 아닌 아홉 명이었던 것이다.

아홉 명의 난쟁이는 모두 자신이 "백설 공주와 일곱 난쟁이"의 주인공이라고 주장했다. 뛰어난 수학적 직관력을 가지고 있던 백설공주는, 다행스럽게도 일곱 난쟁이의 키의 합이 100이 됨을 기억해 냈다.

아홉 난쟁이의 키가 주어졌을 때, 백설공주를 도와 일곱 난쟁이를 찾는 프로그램을 작성하시오.

 

입력

아홉 개의 줄에 걸쳐 난쟁이들의 키가 주어진다. 주어지는 키는 100을 넘지 않는 자연수이며, 아홉 난쟁이의 키는 모두 다르며, 가능한 정답이 여러 가지인 경우에는 아무거나 출력한다.

 

출력

일곱 난쟁이의 키를 오름차순으로 출력한다. 일곱 난쟁이를 찾을 수 없는 경우는 없다.

 

예제 입출력


Algorithm

완전 탐색 이용
1. 난쟁이의 키를 리스트로 입력
2. 두 개씩 뺀 후 리스트의 합이 100이 되는지 확인

 

Code

import sys
input = sys.stdin.readline

heights = [0 for _ in range(9)]
for i in range(9):
    heights[i] = int(input())

# 리스트 오름차순
heights.sort()

# 리스트에서 두개씩 빼어 리스트의 합이 100이 되는지 확인
temp = []
for i in range(len(heights)):
    for j in range(i, len(heights)):
        if sum(heights[:i]+heights[i+1:j]+heights[j+1:]) == 100:
            temp += heights[:i] + heights[i+1:j] + heights[j+1:]
            break
    if len(temp) > 0:
        break
    
answer = ''
for i in temp:
    answer += str(i) + '\n'
print(answer)

메모리: 30860 KB
시간: 68 ms

반응형

+ Recent posts