728x90
반응형

www.acmicpc.net/problem/2667

 

2667번: 단지번호붙이기

<그림 1>과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여

www.acmicpc.net

문제

<그림 1>과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여기서 연결되었다는 것은 어떤 집이 좌우, 혹은 아래위로 다른 집이 있는 경우를 말한다. 대각선상에 집이 있는 경우는 연결된 것이 아니다. <그림 2>는 <그림 1>을 단지별로 번호를 붙인 것이다. 지도를 입력하여 단지수를 출력하고, 각 단지에 속하는 집의 수를 오름차순으로 정렬하여 출력하는 프로그램을 작성하시오.

입력

첫 번째 줄에는 지도의 크기 N(정사각형이므로 가로와 세로의 크기는 같으며 5≤N≤25)이 입력되고, 그 다음 N줄에는 각각 N개의 자료(0혹은 1)가 입력된다.

출력

첫 번째 줄에는 총 단지수를 출력하시오. 그리고 각 단지내 집의 수를 오름차순으로 정렬하여 한 줄에 하나씩 출력하시오.

예제 입력 1

7
0110100
0110101
1110101
0000111
0100000
0111110
0111000

예제 출력 1

3
7
8
9

 

[문제 풀이]

일단 <그림1>에서 1이 적힌 곳을 찾아서 0이 나올때까지 끝까지 탐색을 시켜줘야된다. 여기서 깊이 우선 탐색을 생각해 낼 수 있다. 지도에서 공간이 상, 하, 좌, 우로 연결되어 있다고 표현할 수 있으므로 그래프 형태로 모델링 할 수 있다. 

 

1. 특정한 지점의 주변 상, 하, 좌, 우를 살펴본 뒤에 주변 지점 중에서 값이 '0'이면서 아직 방문하지 않은 지점이 있다면 해당 지점을 방문한다.

2. 방문한 지점에서 다시 상, 하, 좌, 우를 살펴보면서 방문을 다시 진행하면, 연결된 모든 지점을 방문할 수 있다.

 

n = int(input())
graph=[]#지도
apt=[]
for _ in range(n):
    graph.append(list(map(int,input())))

def dfs(x,y):
    global cnt
    if x<=-1 or x>=n or y<=-1 or y>=n:
        return False
    if graph[x][y]==1:
        graph[x][y]=0
        cnt+=1
        dfs(x-1,y)
        dfs(x+1,y)
        dfs(x,y+1)
        dfs(x,y-1)
        return True
    return False
cnt=0
for i in range(n):
    for j in range(n):
        if dfs(i,j)==True:
            apt.append(cnt)
            cnt =0
apt.sort()
print(len(apt))
for i in range(len(apt)):
    print(apt[i])

코드를 설명해보겠다.

일단 출력해야 되는 것은 2개이다. 아파트 단지의 개수와 단지 안에 아파트 수이다. apt 리스트에는 아파트 수가 담겨있게 하고 단지 수는 len(apt)로 구할 생각을 했다.

 

위에서 말했듯이 dfs로 풀었다. 일단 dfs함수에서 x,y 가 갈 수 없는 곳을 갔을 때는 False를 return해 주었다.

그리고 graph에서 값이 1일때 단지 수를 세면 되니까 1일때 graph의 값을 방문했다는 의미로 0을 대입해주고 아파트 수 즉 cnt를 1씩 늘여간다. 

 

그리고 dfs함수로 상, 하, 좌, 우를 방문한다.

 

n*n 반복문으로 apt를 구한다.

728x90
반응형
728x90
반응형

리스트 컴프리헨션

: 리스트 컴프리헨션(List Comprehension)이란 기존 리스트를 기반으로 새로운 리스트를 만들어내는 구문으로 파이썬의 대표적인 특징이다. 짧게 한 줄로 만들 수 있는 파이썬의 문법 이라고 생각하면 된다.

 

 

예를 들면, 다음과 같다.

#1
#[ ( 변수를 활용한 값 ) for ( 사용할 변수 이름 ) in ( 순회할 수 있는 값 )]
 a = [n*2 for n in range(1,10+1) if n%2==1]


#2
a=[]
for n in range(1,10+1):
    if n%2==1:
        a.append(n*2)

1번과 2번의 결과값은 같다. 1부터 10까지 중 홀수를 구하는 식이다. 그러나 리스트 컴프리헨션을 쓰면 2번처럼 길게 풀어서 쓸 필요가 없어지는 것이다. 리스트 뿐만 아니라 딕셔너리 등이 가능하도록 추가됐다.


//나눗셈 연산자

파이썬에서는 / 하나만 사용하면 float형태로 구하기 때문에 원하는 몫을 구할 수 없다. //를 이용해서 몫을 구하면 된다.

만약 나머지를 구하려면 %연산자를 사용하면 된다.

그리고 몫과 나머지를 모두 구하려면 divmod()함수를 사용하면 된다.

divmod(5,3)
#(1,2)

print

코딩 테스트 문제 풀이 과정에서 디버깅을 할 때 가장 자주 쓰는 명령은 print()다.

가장 쉽게 값을 출력하는 방법은 콤마(,)로 구분하는 것이다. 이 경우 한 칸 공백이 디폴트로 설정되어 있다.

print('A1','B2')
#A1 B2
#sep 파라미터로 구분자를 콤마로 지정
print('A1','B2',sep=',')
#A1,B2

print()함수는 항상 줄바꿈을 하기 때문에 긴 루프의 값을 반복적으로 출력하면 디버깅하기가 어려워서 end파라미터를 공백으로 처리하여 줄바꿈을 하지 않도록 제한하자.

print('aa',end=' ')
print('bb')
#aa bb

리스트를 출력할 때는 join()으로 묶어서 처리한다.

a = ['A','B']
print(' ',join(a))
#A B

pass

코딩을 하다 보면 일단 코드의 전체 골격을 잡아 놓고 내부에서 처리할 내용은 차근차근 생각하며 만들겠다는 의도로 다음과 같이 코딩하는 경우가 있다. 

class MyClass(Object):
 def method_a(self):
 
 def method_b(self):
  print("Method B")
  
C=MyClass()

그러나 이 클래스는 실행이 되지 않는다. 

 

이 문제는 method_a()가 아무런 처리를 하지 않았기 때문에 엉뚱하게 method_b()에서 오류가 발생한 것인데, 필요한 오류이긴 하나 한참 개발을 하던 중에 이런 오류에 맞닥뜨리게 되면 생각보다 처리하기가 번거롭다. pass는 이런 오류를 막는 역할을 한다. 다음과 같이 pass를 method_a()에 삽입해 간단히 처리할 수 있다.

 

class MyClass(Object):
 def method_a(self):
  pass
 
 def method_b(self):
  print("Method B")
  
C=MyClass()

 

파이썬에서 pass는 널 연산(Null Operation)으로 아무것도 하지 않는 기능이다. 이처럼 아무 역할을 하지 않는 pass를 지정하면, 오류를 방지할 수 있다. 

728x90
반응형
728x90
반응형

 강남역에 엄청난 폭우가 쏟아진다고 가정합시다. 정말 재난 영화에서나 나올 법한 양의 비가 내려서, 고층 건물이 비에 잠길 정도입니다.

 

 그렇게 되었을 때, 건물과 건물 사이에 얼마큼의 빗물이 담길 수 있는지 알고 싶은데요. 그것을 계산해 주는 함수 trapping_rain을 작성해 보려고 합니다.

 

 함수 trapping_rain은 건물 높이 정보를 보관하는 리스트 buildings를 파라미터로 받고, 담기는 빗물의 총량을 리턴해 줍니다.

 

 예를 들어서 파라미터 buildings로 [3, 0, 0, 2, 0, 4]가 들어왔다고 합시다. 그러면 0번 인덱스에 높이 3의 건물이, 3번 인덱스에 높이 2의 건물이, 5번 인덱스에 높이 4의 건물이 있다는 뜻입니다. 1번, 2번, 4번 인덱스에는 건물이 없습니다.

 

그러면 아래의 사진에 따라 총 10 만큼의 빗물이 담길 수 있습니다. 따라서 trapping_rain 함수는 10을 리턴하는 거죠.

 

 

이번에는 파라미터 buildings로 [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]가 들어왔다고 합시다. 그러면 아래의 사진에 따라 총 6 만큼의 빗물이 담길 수 있습니다. 따라서 trapping_rain 함수는 6을 리턴하는 거죠

 

이 정보를 기반으로, trapping_rain 함수를 작성해 보세요!

 

예시

# 테스트
print(trapping_rain([3, 0, 0, 2, 0, 4]))
print(trapping_rain([0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]))
10
6

 

[해설]

빗물이 담기는 양을 계산하려면 각각의 index에 해당하는 빗물의 양을 모두 더하면 된다. 각각의 index에 빗물의 양을 계산하려면 규칙을 파악해야 한다. 

 

 먼저 예시를 보고 알 수 있는 점은 0번 인덱스와 마지막 인덱스에는 빗물이 담길 수 없다. 그리고 더 큰 건물들 사이에 끼어 있으면 빗물이 담긴다는 것을 알 수 있다. 그리고 구해야 할 것은 얼마의 빗물이 담기는지 알아야 된다.

 

다음 그림에서 4번 인덱스를 보자. 4번 인덱스는 왼쪽으로 가장 높은 건물은 3번 인덱스에 있고, 4번 인덱스의 오른쪽으로 가장 높은 건물은 7번 인덱스에 있다. 3번 인덱스의 건물은 높이가 2이고, 7번 인덱스의 건물은 높이가 3인다. 그리고 4번 인덱스에 담긴 빗물의 양은 1이다. 

 

물이 담기는 것은 4번 인덱스 건물의 높이인 1부터 시작해서, 3번 인덱스와 7번 인덱스의 건물 중 더 낮은 높이인 2까지이다. 그래서 1 만큼의 빗물만 담기는 것이다. 

 

1. 현재 인덱스의 왼쪽에서 가장 높은 건물의 높이를 구한다.

2. 현재 인덱스의 오른쪽에서 가장 높은 건물의 높이를 구한다.

3. 왼쪽과 오른쪽에서 구한 최대값은 2개인데 이 중 더 낮은 건물의 높이를 구한다.

4. 그 높이에서 현재 인덱스에 있는 건물의 높이를 뺀다.

 

def trapping_rain(buildings):
    total=0
    for i in range(1,len(buildings)-1):
        max_left=max(buildings[:i])
        max_right=max(buildings[i:])

        upper_bound = min(max_left,max_right)

        total += max(0,upper_bound-buildings[i])
    return total
# 테스트
print(trapping_rain([3, 0, 0, 2, 0, 4]))
print(trapping_rain([0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]))
728x90
반응형
728x90
반응형

www.acmicpc.net/problem/2798

 

2798번: 블랙잭

첫째 줄에 카드의 개수 N(3 ≤ N ≤ 100)과 M(10 ≤ M ≤ 300,000)이 주어진다. 둘째 줄에는 카드에 쓰여 있는 수가 주어지며, 이 값은 100,000을 넘지 않는 양의 정수이다. 합이 M을 넘지 않는 카드 3장

www.acmicpc.net

문제

카지노에서 제일 인기 있는 게임 블랙잭의 규칙은 상당히 쉽다. 카드의 합이 21을 넘지 않는 한도 내에서, 카드의 합을 최대한 크게 만드는 게임이다. 블랙잭은 카지노마다 다양한 규정이 있다.

한국 최고의 블랙잭 고수 김정인은 새로운 블랙잭 규칙을 만들어 상근, 창영이와 게임하려고 한다.

김정인 버전의 블랙잭에서 각 카드에는 양의 정수가 쓰여 있다. 그 다음, 딜러는 N장의 카드를 모두 숫자가 보이도록 바닥에 놓는다. 그런 후에 딜러는 숫자 M을 크게 외친다.

이제 플레이어는 제한된 시간 안에 N장의 카드 중에서 3장의 카드를 골라야 한다. 블랙잭 변형 게임이기 때문에, 플레이어가 고른 카드의 합은 M을 넘지 않으면서 M과 최대한 가깝게 만들어야 한다.

N장의 카드에 써져 있는 숫자가 주어졌을 때, M을 넘지 않으면서 M에 최대한 가까운 카드 3장의 합을 구해 출력하시오.

입력

첫째 줄에 카드의 개수 N(3 ≤ N ≤ 100)과 M(10 ≤ M ≤ 300,000)이 주어진다. 둘째 줄에는 카드에 쓰여 있는 수가 주어지며, 이 값은 100,000을 넘지 않는 양의 정수이다.

합이 M을 넘지 않는 카드 3장을 찾을 수 있는 경우만 입력으로 주어진다.

출력

첫째 줄에 M을 넘지 않으면서 M에 최대한 가까운 카드 3장의 합을 출력한다.

예제 입력 1

5 21

5 6 7 8 9

예제 출력 1

21

예제 입력 2

10 500

93 181 245 214 315 36 185 138 216 295

예제 출력 2

497

 

[문제 해설]

먼저 해볼 수 있는 생각은 카드를 3개 뽑아서 m을 넘지않는 수를 뽑는 것이다. 간단하게 3중 포문을 돌려서 3개의 카드가 같지 않고 m을 넘지 않을때 값을 저장해 둔다. 이 값들 중 최대의 것을 뽑으면 된다. m보다 작은 값이 나올 수도 있으므로 나온 값들 중 최대를 뽑으면 되는것이다.

1. m을 넘는 경우 출력을 안하는 것을 생각해 주어야 한다.

2. 3중 for문을 돌릴 때 3개가 동일한 값이 들어가면 안되니까 조건을 추가해준다.

n,m = map(int,input().split())
cards=list(map(int,input().split()))
answer=0
for i in cards:
    for j in cards:
        for k in cards:
            if i!=j and i!=k and j!=k:
                sum=i+j+k
                if sum>m:
                    continue
                else:
                    answer=max(answer,sum)
print(answer)
728x90
반응형
728x90
반응형

재귀 함수란 자기자신을 다시 호출하는 함수를 의미한다.

 

def recursive_function():
	print("재귀 함수를 호출합니다")
    recursive_function()
    
recursive_function()

 

이 코드를 실행하면 '재귀 함수를 호출합니다' 라는 문자열을 무한히 출력한다. 여기서 정의한 recursive_function()이 자기 자신을 계속해서 추가로 불러오기 때문이다. 물론 어느 정도 출력하다가 오류 메시지를 출력하고 멈출 것이다. 

 

 재귀 함수를 쓸 때는 종료 조건이 중요하다. 다음 코드는 i가 100이 될 때 종료한다.

 

def recursive_function(i):
	if i==100:
    return
    print(i)
    recursive_function(i+1)
   
recursive_function(1)

 

컴퓨터 내부에서 재귀 함수의 수행은 스택 자료구조를 사용한다. 함수를 계속 호출했을 때 가장 마지막에 호출한 함수가 먼저 수행을 끝내야 그 앞의 함수 호출이 종료되기 때문이다. 

 

따라서 스택 자료구조를 활용해야 하는 상당수 알고리즘은 재귀 함수를 이용해서 간편하게 구현될 수 있다. DFS가 대표적인 예이다. 

 

재귀 함수에 접근하기 위해서는 2가지 case를 고려해야 한다. 재귀 함수에는 recursive case 와 base case가 있다.

Recursive case : 현 문제가 너무 커서, 같은 형태의 더 작은 부분 문제를 재귀적으로 푸는 경우

Base case : 이미 문제가 충분히 작아서, 더 작은 부분 문제로 나누지 않고도 바로 답을 알 수 있는 경우

 

예를 들어, some_list라는 배열을 파라미터로 받고, 뒤집힌 리스트를 리턴해 주는 재귀 함수를 만들어보자.

 

먼저 Base case를 생각해보자. Base case는 some_list의 길이가 1이거나 0인 경우이다. Base Case가 종료 조건이라고 생각하면 된다.

 

이때는 아무 조치없이 some_list 자체를 그냥 반환하면 된다. 

 

def flip(some_list):
	#base case
    if len(some_list)==0 or len(some_list)==1:
    	return some_list

 

그리고 현재 문제가 너무 커서 바로 풀지 못하는 경우가 recursive case이다. some_list가 1보다 큰 경우에는 바로 답을 알지 못하기 때문에 부분 문제를 풀어야 된다.

 

def flip(some_list):
    if len(some_list)==0 or len(some_list)==1:
        return some_list
    return some_list[-1:]+flip(some_list[:-1])

 

시간복잡도는 some_list의 길이를 n이라고 하면 some_list[:-1]은 시간 복잡도가 O(n-1)이다.

flip함수는 재귀적으로 n번 실행되고 각 호출은 O(n)이기 때문에 시간 복잡도는 O(n^2)이다.

 

728x90
반응형

'알고리즘 > 알고리즘 이론' 카테고리의 다른 글

DFS / BFS  (0) 2021.04.12
정렬(Sort)  (0) 2021.04.12
브루트 포스 (Brute Force)  (0) 2021.03.18
다이나믹 프로그래밍  (0) 2021.03.08
알고리즘 평가  (0) 2021.03.05
728x90
반응형

하노이 탑 

www.acmicpc.net/problem/1914

 

1914번: 하노이 탑

세 개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다. 각 원판은 반경이 큰 순서대로 쌓여있다. 이제 수도승들이 다음 규칙에 따라 첫 번째 장대에서 세 번째 장대로

www.acmicpc.net

문제

세 개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다. 각 원판은 반경이 큰 순서대로 쌓여있다. 이제 수도승들이 다음 규칙에 따라 첫 번째 장대에서 세 번째 장대로 옮기려 한다.

  1. 한 번에 한 개의 원판만을 다른 탑으로 옮길 수 있다.
  2. 쌓아 놓은 원판은 항상 위의 것이 아래의 것보다 작아야 한다.

이 작업을 수행하는데 필요한 이동 순서를 출력하는 프로그램을 작성하라. 단, 이동 횟수는 최소가 되어야 한다.

아래 그림은 원판이 5개인 경우의 예시이다.

입력

첫째 줄에 첫 번째 장대에 쌓인 원판의 개수 N (1 ≤ N ≤ 100)이 주어진다.

출력

첫째 줄에 옮긴 횟수 K를 출력한다.

N이 20 이하인 입력에 대해서는 두 번째 줄부터 수행 과정을 출력한다. 두 번째 줄부터 K개의 줄에 걸쳐 두 정수 A B를 빈칸을 사이에 두고 출력하는데, 이는 A번째 탑의 가장 위에 있는 원판을 B번째 탑의 가장 위로 옮긴다는 뜻이다. N이 20보다 큰 경우에는 과정은 출력할 필요가 없다.

예제 입력 1

3

예제 출력 1

7 1 3 1 2 3 2 1 3 2 1 2 3 1 3

 

[문제 해설]

막대가 3개가 있을때 생각해보자. 맨 밑에 젤 큰 원판 말고 나머지를 두번째 막대에 옮기고, 젤 큰 원판을 3번째 막대로 옮긴 뒤에, 두번째 막대에 있는 원판들을 3번째 막대로 옮기면 된다. 이걸 재귀 함수를 사용해서 풀면 된다.

 

mid_peg=(6-start_peg-end_peg) 인 이유 1,2,3 세 개니까 다 더하면 6임. 거기서 start_peg랑 end_peg를 빼면 나머지가 나옴. 거기로 옮겨야됨.

 

재귀함수에는 recursive case와 base case가 있다.

 

1. 원판이 없을때에는 아무것도 안해도 게임이 끝남( base case )

def hanoi(num_disks,start_peg,end_peg):
	if num_disks==0:
    	return

2. 원판이 하나 있을 경우에는 1번 기둥에서 3번 기둥으로 옮기면 끝난다. ( base case )

 

3. 원판이 2개인 경우에는 1번 원판을 1번 기둥에서 2번 기둥으로 옮기고, 2번 원판을 1번기둥에서 3번기둥으로 옮기고 1번 원판을 2번 기둥에서 3번 기둥으로 옮기면 된다.

 

4. 3번을 생각하면 recursive case에 관해서도 구할 수 있다.

def move_check(start,end):
    print(start,end)

def hanoi(move,start,end):
    if move==1:
        return move_check(start,end)
    other=6-start-end
    hanoi(move-1,start,other)
    move_check(start,end)
    hanoi(move-1,other,end)

일단 move_check(start,end) 함수는 start에서 end로 가는 것을 출력해 주는 함수라고 생각하면 된다.

그 다음 hanoi(move,start,end) 함수를 보자. 이 함수를 만든 것은 move를 start에서 end로 옮긴다고 생각하면 된다.

other은 start와 end가 아닌 나머지 기둥의 숫자이다. 1,2,3 세 개의 기둥이 있으므로 1 +2 + 3 = 6이다.

6에서 start와 end를 빼주면 other이 나올 것이다.

일단 맨 밑의 기둥 빼고 나머지를 other기둥에 두고 맨 밑에 탑을 end에 두고 other기둥에 있는 것을 end에 두면 된다.

이게 순서대로

hanoi(move-1,start,other)
move_check(start,end)
hanoi(move-1,other,end)

이렇게 되는 것이다. move_check로 하나하나 출력할 수 있다.

 

 

 

!!이 문제를 풀 때 주의할 점

1. 총 옮겨야 되는 것을 먼저 출력해 주어야 된다. 총 수를 구할려면 규칙을 찾으면 된다.

  탑이 하나일 때는 1번, 두 개일 때는 3번, 세 개일때는 7번... 규칙을 찾으면 sum*2+1을 하면 된다는 것이 보인다.

  이것을 먼저 출력해주자.

sum=0
for i in range(n):
    sum=sum*2+1

2. 이 문제에서 출력 초과가 계속 난다면 n이 20이 넘을때 과정을 생략해도 된다는 문제 설명을 읽었는지 확인하자!!

(나도 이것때매 문제를 계속 다시 보았다)

if n>20:
    print(sum)
else:
    print(sum)
    hanoi(n,1,3)

 

[정답]

n = int(input())
k=0
def move_check(start,end):
    print(start,end)
def hanoi(move,start,end):
    if move==1:
        return move_check(start,end)
    other=6-start-end
    hanoi(move-1,start,other)
    move_check(start,end)
    hanoi(move-1,other,end)
sum=0
for i in range(n):
    sum=sum*2+1

if n>20:
    print(sum)
else:
    print(sum)
    hanoi(n,1,3)
728x90
반응형
728x90
반응형

www.acmicpc.net/problem/2805

 

2805번: 나무 자르기

첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보

www.acmicpc.net

문제

상근이는 나무 M미터가 필요하다. 근처에 나무를 구입할 곳이 모두 망해버렸기 때문에, 정부에 벌목 허가를 요청했다. 정부는 상근이네 집 근처의 나무 한 줄에 대한 벌목 허가를 내주었고, 상근이는 새로 구입한 목재절단기를 이용해서 나무를 구할것이다.

목재절단기는 다음과 같이 동작한다. 먼저, 상근이는 절단기에 높이 H를 지정해야 한다. 높이를 지정하면 톱날이 땅으로부터 H미터 위로 올라간다. 그 다음, 한 줄에 연속해있는 나무를 모두 절단해버린다. 따라서, 높이가 H보다 큰 나무는 H 위의 부분이 잘릴 것이고, 낮은 나무는 잘리지 않을 것이다. 예를 들어, 한 줄에 연속해있는 나무의 높이가 20, 15, 10, 17이라고 하자. 상근이가 높이를 15로 지정했다면, 나무를 자른 뒤의 높이는 15, 15, 10, 15가 될 것이고, 상근이는 길이가 5인 나무와 2인 나무를 들고 집에 갈 것이다. (총 7미터를 집에 들고 간다) 절단기에 설정할 수 있는 높이는 양의 정수 또는 0이다.

상근이는 환경에 매우 관심이 많기 때문에, 나무를 필요한 만큼만 집으로 가져가려고 한다. 이때, 적어도 M미터의 나무를 집에 가져가기 위해서 절단기에 설정할 수 있는 높이의 최댓값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000)

둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보다 크거나 같기 때문에, 상근이는 집에 필요한 나무를 항상 가져갈 수 있다. 높이는 1,000,000,000보다 작거나 같은 양의 정수 또는 0이다.

출력

적어도 M미터의 나무를 집에 가져가기 위해서 절단기에 설정할 수 있는 높이의 최댓값을 출력한다.

예제 입력 1

4 7

20 15 10 17

예제 출력 1

15

 

[문제 해설]

H높이보다 큰 것은 (높이 - H)가 될 것이고 높이보다 작으면 잘리지 않을 것이다. 적당한 H 높이를 찾는 방법인데 최적의 길이를 찾아야되기 때문에 요리조리 해보면서 구해야 된다. 최적의 수를 찾는 것이기 때문에 sorting하는 방법이다. 알고리즘은 binary_search를 사용해서 풀면 시간도 적절하게 나온다. 

import sys
sys.stdin.readline

n,m = map(int,input().split())
tree=list(map(int,input().split()))

start = 1
end = max(tree)
ans=0

while start<=end:
    mid=(start+end)//2
    result=0
    for i in tree:
        if mid<i:
            result+=i-mid
    if result>=m:
        ans=mid
        start=mid+1
    elif result<m:
        end=mid-1
print(ans)
728x90
반응형
728x90
반응형

www.acmicpc.net/problem/1026

 

1026번: 보물

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

www.acmicpc.net

문제

옛날 옛적에 수학이 항상 큰 골칫거리였던 나라가 있었다. 이 나라의 국왕 김지민은 다음과 같은 문제를 내고 큰 상금을 걸었다.

길이가 N인 정수 배열 A와 B가 있다. 다음과 같이 함수 S를 정의하자.

S = A[0]×B[0] + ... + A[N-1]×B[N-1]

S의 값을 가장 작게 만들기 위해 A의 수를 재배열하자. 단, B에 있는 수는 재배열하면 안 된다.

S의 최솟값을 출력하는 프로그램을 작성하시오.

입력

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

출력

첫째 줄에 S의 최솟값을 출력한다.

예제 입력 1

5

1 1 1 6 0

2 7 8 3 1

예제 출력 1

18

힌트

A를 {1, 1, 0, 1, 6}과 같이 재배열하면 된다.

 

[문제 해설]

일단 B에 있는 수들을 재배열하면 안되고 A에 있는 수들을 재배열하여 최솟값을 구해야 한다. B에 있는 수들 중 제일 큰 수에 A의 제일 작은 수를 배치하면 된다. 사실 B를 정렬하면 sort(reverse=True)를 통하여 A와 곱하면 되지만 조건에서 그렇게 하지 말라고 하였기 때문에 새로운 방법을 고안해야된다. 

A배열의 제일 작은 수와 B배열의 제일 큰 수를 곱해주고 이 제일 작은수와 제일 큰수는 빼주고 다시 sort해서 반복해 주면 된다. 

n = int(input())

a = list(map(int, input().split()))
b = list(map(int, input().split()))

s = 0
for i in range(n):
    s += min(a_list) * max(b_list)
    a.pop(a_list.index(min(a)))
    b.pop(b_list.index(max(b)))

print(s)
728x90
반응형

+ Recent posts