AndroidTeacher

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

문제 설명

농부 상근이는 마당에 심기 위한 나무 묘목 n개를 구입했다. 묘목 하나를 심는데 걸리는 시간은 1일이고, 상근이는 각 묘목이 다 자라는데 며칠이 걸리는지 정확하게 알고 있다.

상근이는 마을 이장님을 초대해 자신이 심은 나무를 자랑하려고 한다. 이장님을 실망시키면 안되기 때문에, 모든 나무가 완전히 자란 이후에 이장님을 초대하려고 한다. 즉, 마지막 나무가 다 자란 다음날 이장님을 초대할 것이다.

상근이는 나무를 심는 순서를 신중하게 골라 이장님을 최대한 빨리 초대하려고 한다. 이장님을 며칠에 초대할 수 있을까?

풀이 과정

나무가 모두 자라는데 걸리는 시간은 정해져 있고, 나무의 심는 순서는 내가 마음대로 정할 수 있는 상황이다.

최대한 빨리 나무들을 모두 길러야 하기 때문에 자라는데 오래 걸리는 나무부터 심어야 할 것이다.

그래서, 나무들의 일수를 먼저 내림차순으로 정렬을 한다.

그리고, 마지막에 자라는 나무를 찾아야 한다.

예를 들어, 4 3 2 2 나무를 심게 되면

4일짜리 나무가 가장 오래 걸리므로 4일짜리 나무를 처음 심게 되지만,

처음 4일짜리 나무가 모두 자라나는 동안 마지막의 2일짜리 나무는 모두 자라지 못한다.

따라서, 나무를 심는데 걸리는 일수의 최댓값을 저장해주며 이를 필요할 때 마다 바꿔주는 과정이 필요하다.

4일짜리 나무를 처음 심은 날을 1일이라고 하면,

이 나무가 모두 자라는 일은 5일이 될 것이며 이 때, 4번째로 심은 2일짜리 나무는 하루가 더 필요한 상황이다.

그래서 max_days < i + days[i] 의 조건문을 이용해 최종적으로 자라나는 나무를 탐색한 후에

max값을 갱신하면 된다.

그리고 마지막에 +2일을 하여, 처음 심는 1일과 마지막 1일을 더해주면 된다.

(이장님은 다음날 초대하기로 하였으며, 나무를 심는데는 1일이 걸리므로 심는날 1일을 제외해야 한다.)

n = int(input())
days = list(map(int, input().split()))

days.sort(reverse=True)

max_days = days[0]

if n == 1:
    print(n + 2)
else:
    for i in range(1, n):
        if max_days < (i + days[i]):
            max_days = i + days[i]

    result = max_days + 2
    print(result)

https://github.com/HongEunho

전체 문제 & 코드는 위의 깃에 정리되어 있습니다.

팔로우 & 맞팔은 환영입니다 !

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

문제 설명

단어 수학 문제는 N개의 단어로 이루어져 있으며, 각 단어는 알파벳 대문자로만 이루어져 있다. 이때, 각 알파벳 대문자를 0부터 9까지의 숫자 중 하나로 바꿔서 N개의 수를 합하는 문제이다. 같은 알파벳은 같은 숫자로 바꿔야 하며, 두 개 이상의 알파벳이 같은 숫자로 바뀌어지면 안 된다.

예를 들어, GCF + ACDEB를 계산한다고 할 때, A = 9, B = 4, C = 8, D = 6, E = 5, F = 3, G = 7로 결정한다면, 두 수의 합은 99437이 되어서 최대가 될 것이다.

N개의 단어가 주어졌을 때, 그 수의 합을 최대로 만드는 프로그램을 작성하시오.

풀이 과정

단어에 등장하는 알파벳을 0~9중의 숫자 중 하나와 매치한다. (단, 수의 중복은 없다. A에 9를 썼으면 B에 9 사용불가)

ABCDE이면 자리수로 봤을 때 A가 가장 큰 비중을 차지하므로 ( 10^4 = 10000 ) A에 9를 매칭시키는 것이 좋을 것이다.

이렇게 가장 큰 비율을 차지하는 알파벳에 최대의 수를 부여해야 하므로

그리디 알고리즘으로 해석할 수 있다.

이 문제는 그리디 알고리즘 중에서도 꽤 까다로운 문제였다.

1. 먼저, 알파벳을 딕셔너리에 저장한다.
   이 때, 단어의 길이에 따라 알파벳의 자릿수가 정해지므로 자릿수를 체크하여 그 자리에 맞는 값을 매칭시킨다.
   { 'A' : 100, 'B' : 1010, 'C': 1 ... }
2. 매칭을 완료한 후에, dict의 value만 가져와서 리스트에 내림차순으로 정렬한다.
   그럼, 가장 큰 비율을 차지하는 것 부터 앞에 등장할 것이다.
   [11000, 10000, 1000, 100 ... ]
   
   
3. 이 리스트의 첫 수 부터 9를 곱하면 된다.
   그 다음 8, 7, ....
   이렇게 곱하면 가장 큰 비율을 차지하는 알파벳에 가장 큰 수를 부여하게 됨으로써 답을 도출해 낼 수 있을 것이다.

↓ 설명과 함께 첨부한 코드 ↓

import sys

n = int(sys.stdin.readline())

alpha = [] # 단어를 저장할 리스트
alpha_dict = {} # 단어 내의 알파벳별로 수를 저장할 딕셔너리
numList = [] # 수를 저장할 리스트

for i in range(n): # 단어를 입력받음
    alpha.append(sys.stdin.readline().rstrip())

for i in range(n): # 모든 단어에 대해서
    for j in range(len(alpha[i])): # 단어의 길이만큼 실행
        if alpha[i][j] in alpha_dict: # 단어의 알파벳이 이미 dict에 있으면
            alpha_dict[alpha[i][j]] += 10 ** (len(alpha[i])-j-1) # 자리에 맞게 추가 ( 1의 자리면 1 )
        else:   # 자리에 없으면 새로 추가 ( 10의 자리면 10 )
            alpha_dict[alpha[i][j]] = 10 ** (len(alpha[i])-j-1)

for val in alpha_dict.values(): # dict에 저장된 수들을 모두 리스트에 추가
    numList.append(val)

numList.sort(reverse=True) # 수들을 내림차순 정렬

sum = 0
pows = 9
for i in numList: # 첫 번째 부터 가장 큰 부분을 차지하므로 9를 곱해준다
    sum += pows * i
    pows -= 1
# 내려갈수록 그 알파벳이 차지하는 비중이 적으므로 -1 
print(sum)

https://github.com/HongEunho

전체 문제 & 코드는 위의 깃에 정리되어 있습니다.

팔로우 & 맞팔은 환영입니다 !

문제 설명

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

0과 1로 이루어진 행렬 A 와 행렬 B가 주어질 때, 행렬 A를 행렬 B로 전환하는데 필요한 횟수를 구하는 문제이다.

이 때, 1회 전환하다는 것은 3x3의 행렬을 뒤집는 것이다.

예를 들어,

000                     111

010                     101

111  을 뒤집으면   000 이 된다.

풀이 과정

이 문제는 그리디 알고리즘으로 접근할 수 있다.

변환 전의 행렬을 A, 전환 후의 행렬을 B라고 하자.

현재 A 행렬의 내 위치에서 B 행렬과 일치하지 않는 부분이 있다면 그 부분부터 3x3 범위안의 행렬을 뒤집어주면 된다.

즉, 현재 내 위치만 보고 내 위치의 원소가 같은 위치에서의 B행렬과 일치하지 않는다면 뒤집는 것이기 때문에

그리디 알고리즘이라고 볼 수 있다.

n, m = map(int, input().split())
graph1 = []
graph2 = []
count = 0

def convertgraph(i, j):			# 3x3을 뒤집는 함수
    for x in range(i, i + 3):
        for y in range(j, j + 3):
            graph1[x][y] = 1 - graph1[x][y]


for i in range(n):				# 변환 전 함수 입력
    graph1.append(list(map(int, input())))

for i in range(n):				# 변환 후 함수 입력
    graph2.append(list(map(int, input())))

for i in range(n - 2):
    for j in range(m - 2):
        if graph1[i][j] != graph2[i][j]: # 일치하지 않는 부분 발생
            convertgraph(i, j)			 # 뒤집고
            count += 1				 	 # 횟수 + 1
flag = 0							# 변환 할 수 있는지 나타내는 변수

for i in range(n):					# 변환 후 일치하는지 확인
    for j in range(m):
        if graph1[i][j] != graph2[i][j]:
            flag = 1
            break

if flag == 1:							# 변환이 불가능 하면 -1 반환
    print(-1)
else:
    print(count)

https://github.com/HongEunho

전체 문제 & 코드는 위의 깃에 정리되어 있습니다.

팔로우 & 맞팔은 환영입니다 !

www.acmicpc.net/problem/2847

문제 설명

첫째 줄에 레벨의 수 N이 주어지고, 다음 줄부터 N+1줄까지 게임 레벨의 난이도가 주어진다.

이전 게임의 레벨은 반드시 다음 게임의 레벨보다 낮아야 하는데, 입력의 상태는 이전 게임이 다음 게임보다 레벨이 높은 경우가 존재한다.

최소한의 횟수로 레벨을 오름차순으로 나타내어야 하며, 레벨 1감소가 1회이다.

풀이 과정

현재 게임이 다음 게임보다 레벨이 낮게 하려면 어떻게 해야할까?

다음 게임의 레벨보다 낮게 설정하면 된다. 단, 최소한의 횟수를 사용하라고 했으므로 다음 게임보다 1만큼 적게 설정해주면 된다.

여기서 주의해야 할 점은, 뒷 게임부터 낮춰주어야 한다는 것이다.

앞에서 부터 낮추게 되면, 다시 앞의 난이도가 뒤의 난이도보다 높아지는 경우가 발생하기 때문이다.

예를 들어 보자.

5 9 4 8 -> 4 9 4 8 -> 4 3 4 8 -> 4 3 7 8

이렇게 되면, 앞의 난이도를 줄였음에도 불구하고 뒤의 난이도가 더 작아지는 상황이 발생한다.

따라서, 뒤의 난이도부터 수정을 해주어야 이런 상황이 발생하지 않는다.

n = int(input())
score = []
for i in range(n):
    score.append(int(input()))

count = 0
for i in range(n-2, -1, -1):
    if score[i] >= score[i+1]:
        count += score[i] - score[i+1] + 1
        score[i] = score[i+1]-1

print(count)

https://github.com/HongEunho

전체 문제 & 코드는 위의 깃에 정리되어 있습니다.

팔로우 & 맞팔은 환영입니다 !

www.acmicpc.net/problem/1449

문제 설명

수리공이 물이 새는 파이프를 테이프로 수리한다. 테이프는 무한 개 갖고 있으며, 최소한의 테이프를 사용하여 수리해야 한다. 물이 새는곳을 막을 때, 그 위치의 좌우로 0.5만큼씩을 더 막아줘야 물이 새지 않는다. 테이프는 자를 수 없으며, 겹칠수는 있다. 또, 물이 새는 곳의 위치는 자연수이다.

풀이 과정

최소한의 개수로 최대의 이익을 취해야 하는 그리디 알고리즘 문제이다.

먼저 테이프의 길이가 1이면, 테이프 1개로 지점을 1개만 막을 수 있다. 그래서 n개의 테이프를 사용해야 한다.

그 외의 경우에는, 테이프를 막는 첫 위치는 첫 지점에서 테이프길이의 절반만큼 더한구간이 되는데, 0.5이전도 막아주어야 하므로 0.5를 빼준 곳이 된다. 그래야 이 위치가 첫구간을 막으면서 첫구간과 가장 멀리 떨어진 곳이 되기 때문이다.

막은 위치를 현재 테이프의 위치로 지정을 해 주고, 현재 테이프가 커버할 수 있는 구간까지는 테이프를 더 붙일 필요가 없다. 

하지만, 현재 테이프가 커버할 수 있는 구간을 벗어나게 되면 새로 테이프를 붙여주어야 하는데,

(다음 물이새는 위치+0.5)가 (현재 테이프가 있는 곳+테이프 길이의 절반) 보다 클 경우에는 새로 테이프를 붙여주어야 하므로, 테이프의 위치를 (다음 물이새는 위치 + 테이프 길이 절반 - 0.5)로 이동시켜야 한다.

이렇게 하면, 최소한의 테이프로 수리를 하게 된다.

n, l = map(int, input().split())
fix = list(map(int, input().split()))
fix.sort()

if l == 1:
    print(n)

else:
    cnt = 1
    cur = fix[0] + l/2 - 0.5

    for i in range(1, n):
        if cur+l/2 < fix[i]+0.5:
            cnt += 1
            cur = fix[i] + l/2 - 0.5
    print(cnt)

https://github.com/HongEunho

전체 문제 & 코드는 위의 깃에 정리되어 있습니다.

팔로우 & 맞팔은 환영입니다 !

www.acmicpc.net/problem/1439

문제 설명

0과 1로만 이루어진 문자열 S이 주어진다. 이 문자열S을 모두 같은 숫자로 이루어진 문자열로 바꾸려고 하는데,

연속된 하나 이상의 숫자를 뒤집을 수 있다. (0을 1로, 1을 0로)

예를 들어, 1001001이 있으면 1001001 -> 1111001 -> 1111111 과 같이 바꿀 수 있다.

주어진 문자열을 바꾸는데 필요한 최소 횟수를 출력하면 된다.

풀이 과정

문제를 보고, 가장 먼저 떠올랐던 풀이법은,

for문을 처음부터 문자열의 끝까지 모두 돌면서 숫자가 바뀌는 순간을 카운트하여

1이 0으로 바뀌는 순간과 0이 1로 바뀌는 순간중 더 작은 값을 출력하도록 하는 방법이다.

하지만, 문제에서 S의 길이는 100만보다 작다고 했으므로, 하나하나 비교하기에는 시간초과가 발생할 것 같다는 생각이 들었다. (하지만 의외로, 이 방법도 시간초과가 발생하지는 않았다.)

그래서 파이썬의 split을 이용하여 split(1)과 split(0)을 하여 더 작은값을 출력하도록 하는 방법을 사용하였다.

1001001을 0으로 구분하면 [ '1', '', '1', '', '1' ] 이고, 1로 구분하면 [ '', '00', '00', '' ] 이다.

즉, 뒤집었을 때 원본이 살아있는 부분만 수가 나타나고 나머지는 ''로 나타나므로 다음과 같이 적용할 수 있다.

import sys
a = sys.stdin.readline().rstrip()

b = a.split("0")
c = a.split("1")

b2 = b.count('')
c2 = c.count('')

print(min(len(b)-b2, len(c)-c2))

https://github.com/HongEunho

전체 문제 & 코드는 위의 깃에 정리되어 있습니다.

팔로우 & 맞팔은 환영입니다 !

www.acmicpc.net/problem/4796

문제 설명

입력으로 L, P, V를 입력받는다. ( 1 < L < P < V )

이는 총 V일간의 휴가기간동안 캠핑장을 연속하는 P일 중, L일동안 이용할 수 있다는 뜻이다.

예를 들어, V = 20, P = 8, L = 5 이면, 

총 휴가기간 20일 중 캠핑장을 연속하는 8일중 5일간 이용할 수 있다는 뜻이다.

그래서 처음 5일을 이용하고 그 뒤 3일은 이용을 못하고 다시 5일을 이용하고 이런 식으로 전개가 된다.

풀이 과정

캠핑장을 P일 꽉채워서 이용할 수 있는 개수는 V // P가 될 것이다.

그리고 나머지는 꽉 채우지 못하고 남은일수만큼 캠핑장에 있게 된다.

단, 남은일수가 캠핑장을 이용할 수 있는 일수보다 많이 남았다면 이용할 수 있는 날만큼만 이용하게 된다.

(예를 들어, 남은 일수가 3일이고 이용할 수 있는 날짜가 1일이면 1일만 이용하게 되는 것이다.

예시로 캠핑장이 연속하는 4일중 1일만 이용가능하고 3일은 이용 불가능한 경우이다.

이를 if문으로 표현하였다.)

i = 0
while True:
    i+=1
    l, p, v = map(int, input().split())
    if l==0 and p==0 and v==0:
        break
    a = v//p
    b = v%p
    if l<b:
        b = l
    print("Case %d: %d" %(i, a*l+b))
    

https://github.com/HongEunho

전체 문제 & 코드는 위의 깃에 정리되어 있습니다.

팔로우 & 맞팔은 환영입니다 !

www.acmicpc.net/problem/1783

문제 설명

병든 나이트는 보통 체스의 나이트와는 다르게 아래의 네가지 방법으로만 움직일 수 있다.

1. 2칸 위로, 1칸 오른쪽
2. 1칸 위로, 2칸 오른쪽
3. 1칸 아래로, 2칸 오른쪽
4. 2칸 아래로, 1칸 오른쪽

이 때, 맵의 크기가 N * M으로 주어질 때, 병든 나이프가 방문할 수 있는 칸의 최대 개수를 구하면 된다.

(단, 이동 횟수가 4번 이상이라면, 4가지 방법을 한 번씩 모두 사용해야 한다.)

풀이 과정

병든나이트는 이동 시, 무조건 오른쪽으로는 이동을 하게 되어있고, 위 아래로는 자유인 상황이다.

1. 세로나 가로의 길이가 1이라면 시작 칸 밖에 방문하지 못한다.

2. 세로의 길이가 2일 경우, 선택권은 2,3 방법 밖에 없다. ( 세로로 한칸씩만 움직이는 방법 )

   이 때는, 가로의 길이가 아무리 길어도 4번이상 움직이지 못하므로, 최댓값은 4가 될 것이다.

3. 가로의 길이가 6이하일 경우에, 4번 이상으로 움직인다고 하면, 1~4번 방법을 모두 써야 하므로 최댓값은 4가 될 것이고, 최소값은 자신 가로의 길이가 될 것이다.

4. 세로의 길이가 3 이상이고, 가로의 길이가 7이상인 경우에는 이동에 제약이 없으므로 오른쪽으로 두 칸을 가야만 하는 강제적인 방법을 빼고는 한칸씩만 움직이면 되므로 m-2 라는 값이 나오게 된다.

이를 코드로 정리하면 다음과 같다.

n, m = map(int, input().split())
if n == 1:
    print(1)
elif n == 2:
    print(min(4, (m-1)//2+1))
elif m <= 6:
    print(min(4, m))
else:
    print(m-2)

https://github.com/HongEunho

전체 문제 & 코드는 위의 깃에 정리되어 있습니다.

팔로우 & 맞팔은 환영입니다 !