728x90
반응형

문제:

2019/10/29 - [Algorithm/Python] - [BOJ]7576. 토마토

 

 위 문제에서 더 발전한 문제로 이제 한 층이 아닌 여러 층에 대해서 토마토가 익는 것이 전이된다.

입력:

첫 줄에는 상자의 크기를 나타내는 두 정수 M,N과 쌓아올려지는 상자의 수를 나타내는 H가 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2<=M<=100,2<=N<=100,1<=H<=100이다. 둘째 줄부터는 가장 밑의 상자부터 가장 위의 상자까지에 저장된 토마토들의 정보가 주어진다. 즉, 둘째줄부터 N개의 줄에는 하나의 상자에 담긴 토마토의 정보가 주어진다. 각 줄에는 상자 가로줄에 들어있는 토마토들의 상태가 M개의 정수로 주어진다. 정수 1은 익은 토마토, 정수 0은 익지 않은 토마토, 정수 -1은 토마토가 들어있지 않은 칸을 나타낸다. 이러한 N개의 줄이 H번 반복하여 주어진다.

출력: 

여러분은 토마토가 모두 익을 때까지 최소 며칠이 걸리는지를 계산하여 출력해야 한다. 만약, 저장될 때부터 모든 토마토가 익어있는 상태이면 0을 출력해야 하고, 토마토가 모두 익지는 못하는 상황이면 -1을 출력해야 한다.

풀이방법:

 이전문제에선 2차원 배열로 받았지만, 이번에는 3차원 배열로 작성한다. 또한 위, 아래로도 이동해야 하기 때문에 dx,dy,dn 세 가지 변수를 사용했다. 이외에는 이전문제와 동일한 풀이로 풀었다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
import sys
m,n,h=map(int,sys.stdin.readline().split())
tomatos=[]
for j in range(h):
    temp=[]
    for i in range(n):
        t=list(map(int,sys.stdin.readline().split()))
        temp.append(t)
    tomatos.append(temp)
queue=[]
for k in range(h):
    for i in range(n):
        for j in range(m):
            if tomatos[k][i][j]==1:
                queue.append((k,i,j))
dx=[0,0,0,0,-1,1]
dy=[0,1,0,-1,0,0]
dh=[1,0,-1,0,0,0]
count=0
while len(queue)!=0:
    count+=1
    temp=[]
    change=False
    for k,i,j in queue[:]:
        for c in range(6):
            nx=j+dx[c]
            ny=i+dy[c]
            nh=k+dh[c]
            if 0<= ny < n and 0<= nx < m and 0<=nh < h:
                if tomatos[nh][ny][nx]==0:
                    tomatos[nh][ny][nx]=1
                    temp.append((nh,ny,nx))
                    change=True
    queue.pop(0)
    queue=temp
    if not change:
        break
        
remain=False
for k in range(h):
    for i in range(n):
        for j in range(m):
            if tomatos[k][i][j]==0:
                remain=True
                break
if not remain:
    print(count-1
else:
    print(-1)
cs

문제링크:

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

728x90
반응형

'Algorithm > Python' 카테고리의 다른 글

[BOJ]14848. 정수 게임  (0) 2019.11.04
[BOJ] 1325. 효율적인 해킹  (0) 2019.10.31
[BOJ]7576. 토마토  (0) 2019.10.29
[BOJ]1049. 기타줄  (0) 2019.10.18
[BOJ]5567. 결혼식  (0) 2019.10.17
728x90
반응형

문제:

철수의 토마토 농장에서는 토마토를 보관하는 큰 창고를 가지고 있다. 토마토는 아래의 그림과 같이 격자 모양 상자의 칸에 하나씩 넣어서 창고에 보관한다.

 

창고에 보관되는 토마토들 중에는 잘 익은 것도 있지만, 아직 익지 않은 토마토들도 있을 수 있다. 보관 후 하루가 지나면, 익은 토마토들의 인접한 곳에 있지 않은 토마토들은 익은 토마토의 영향을 받아 익게 된다. 하나의 토마토의 인접한 곳은 왼쪽, 오른쪽, 앞, 뒤 네 방향에 있는 토마토를 의미한다. 대각선 방향에 있는 토마토들에게는 영향을 주지 못하며, 토마토가 혼자 저절로 익는 경우는 없다고 가정한다. 철수는 창고에 보관된 토마토들이 며칠이 지나면 다 익에 되는지, 그 최소 일수를 알고 싶어 한다.

 

토마토를 창고에 보관하는 격자모양의 상자들의 크기와 익은 토마토들과 익지 않은 토마토들의 정보가 주어졌을 때, 며칠이 지나면 토마토들이 모두 익는지, 그 최소 일수를 구하는 프로그램을 작성하라. 단, 상자의 일부 탄에는 토마토가 들어있지 않을 수도 있다.

입력:

첫 줄에는 상자의 크기를 나타내는 두 정수 M, N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단 2<=M,N<=1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토들의 정보가 주어진다. 즉, 둘째 줄부터 N개의 줄에는 상자에 담긴 토마토의 정보가 주어진다. 하나의 줄에는 상자 가로줄에 들어있는 토마토의 상태가 M개의 정수로 주어진다. 정수 1은 익은 토마토, 정수 0은 잊지 않는 토마토, 정수 -1은 토마토가 들어있지 않은 칸을 나타낸다.

출력:

여러분은 토마토가 모두 익을 때까지의 최소 날짜를 출력해야 한다. 만약, 저장될 때부터 모든 토마토가 익어있는 상태이면 0을 출력해야 하고, 토마토가 모두 익지 못하는 상황이면 -1을 출력해야 한다.

풀이방법:

BFS를 사용해서 풀어야 하는 문제이다. 우선 1이 있는 위치를 파악을 하고 이를 queue에 넣어 준다. 그 뒤에 1을 하나씩 빼면서 옆에 있는 토마토를 익게 만들 수 있는지 계산을 한다. 이 때 change라는 bool 변수를 만들어서 하나의 토마토라도 queue 진행 중에 익게 된다면 True로 바뀌어서 다음 진행을 계속해서 하도록 한다. 만약 익게 되는 토마토가 없어서 False로 남아 있다면 다 익어서 종료가 된 것인지, 혹은 모두 익지 못하는 상황인지 전체를 한 번 탐색하여 파악한다.

처음부터 모두가 익어 있으면 0을 출력해야 하지만 첫 count는 항상 1부터 시작하기 때문에 count-1을 한 값을 출력하면 답을 얻을 수 있다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
m,n=map(int,input().split())
tomatos=[]
for i in range(n):
    t=list(map(int,input().split()))
    tomatos.append(t)
queue=[]
for i in range(n):
    for j in range(m):
        if tomatos[i][j]==1:
            queue.append((i,j))
dx=[0,0,-1,1]
dy=[-1,1,0,0]
count=0
while len(queue)!=0:
    count+=1
    temp=[]
    change=False
    for i,j in queue[:]:
        for c in range(4):
            nx=j+dx[c]
            ny=i+dy[c]
            if 0<= ny < n and 0<= nx < m:
                if tomatos[ny][nx]==0:
                    tomatos[ny][nx]=1
                    temp.append((ny,nx))
                    change=True
    queue.pop(0)
    queue=temp
    if not change:
        break
        
remain=False
for i in range(n):
    for j in range(m):
        if tomatos[i][j]==0:
            remain=True
            break
if not remain:
    print(count-1
else:
    print(-1)
cs

문제링크:

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

728x90
반응형

'Algorithm > Python' 카테고리의 다른 글

[BOJ] 1325. 효율적인 해킹  (0) 2019.10.31
[BOJ]7569. 토마토  (0) 2019.10.30
[BOJ]1049. 기타줄  (0) 2019.10.18
[BOJ]5567. 결혼식  (0) 2019.10.17
[BOJ]1159. 농구 경기  (1) 2019.10.16
728x90
반응형

문제:

Day of Mourning의 기타리스트 강토가 사용하는 기타에서 N개의 줄이 끊어졌다. 따라서 새로운 줄을 사거나 교체해야 한다. 강토는 되도록이면 돈을 적게 쓰려고 한다. 6줄 패키지를 살 수도 있고, 1개 또는 그 이상의 줄을 낱개로 살 수도 있다.

끊어진 기타줄의 개수 N과 기타줄 브랜드 M개가 주어지고, 각각의 브랜드에서 파는 기타줄 6개가 들어있는 패키지의 가격, 낱개로 살 때의  가격이 주어질 때, 적어도 N개를 사기 위해 필요한 돈의 수를 최소로 하는 프로그램을 작성하시오.

입력:

첫째 줄에 N과 M이 주어진다. N은 100보다 작거나 같은 자연수이고, M은 50보다 작거나 같은 자연수이다. 둘째 줄부터 M개의 줄에는 각 브랜드의 패키지 가격과 낱개의 가격이 공백으로 구분하여 주어진다. 가격은 0보다 크거나 같고, 1,000보다 작거나 같은 정수이다.

출력:

첫째 줄에 기타줄을 적어도 N개 사기 위해 필요한 돈의 최솟값을 출력한다.

풀이방법:

여러 개의 기타줄에서 패키지 가격이 가장 작은 값과, 낱개 가격이 가장 작은 값만 필요하다. 이 두 개의 가격을 비교했을 때, 만약 낱개로 6개를 사는 것이 패키지 가격보다 싸다면 모든 기타줄을 낱개로 사는 것이 이득이다.

만약 그렇지 않다면 사야하는 기타줄을 6으로 나눴을 때 그 몫만큼은 패키지로 사는 것이 이득이다. 그 뒤로는 남은 나머지를 낱개로 샀을 때와 패키지로 샀을 때(적어도 N개를 구매하면 되므로 초과해서 사도 괜찮다.) 어떤 것이 이득인지 알아보고 그에 맞게 구매를 해야 한다. (ex 패키지 7 낱개 2면 패키지가 더 이득)  

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
n,m=map(int,input().split())
packages,single=[],[]
for i in range(m):
    p,s=map(int,input().split())
    packages.append(p)
    single.append(s)
minP,minS=min(packages),min(single)
if minP > minS*6:
    print(minS*n)
else:
    p,r=divmod(n,6)
    if minP > minS*r:
        print(minP*p+minS*r)
    else:
        print(minP*(p+1))
cs

문제링크:

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

728x90
반응형

'Algorithm > Python' 카테고리의 다른 글

[BOJ]7569. 토마토  (0) 2019.10.30
[BOJ]7576. 토마토  (0) 2019.10.29
[BOJ]5567. 결혼식  (0) 2019.10.17
[BOJ]1159. 농구 경기  (1) 2019.10.16
[BOJ]1016. 제곱ㄴㄴ수  (0) 2019.10.15
728x90
반응형

문제:

풀이방법:

나갈 때 정보, 들어올 때의 정보가 둘 다 있는 테이블이 필요하므로 둘을 INNER JOIN을 하도록 한다. 그 뒤에 WHERE 절로 IN일 때는 Intact라는 단어를 포함하도록 하고, OUTS일 때는 Intact라는 단어가 없는 경우에 대해서만 출력하도록 했다.

1
2
SELECT I.ANIMAL_ID,I.ANIMAL_TYPE,I.NAME FROM ANIMAL_INS I, ANIMAL_OUTS O WHERE I.ANIMAL_ID = O.ANIMAL_ID
AND I.SEX_UPON_INTAKE LIKE '%Intact%' AND O.SEX_UPON_OUTCOME NOT LIKE '%Intact%' ORDER BY i.ANIMAL_ID;
cs

문제링크:

https://programmers.co.kr/learn/courses/30/lessons/59045

728x90
반응형
728x90
반응형

문제:

상근이는 자신의 결혼식에 학교 동기 중 자신의 친구와 친구의 친구를 초대하기로 했다. 상근이의 동기는 모두 N명이고, 이 학생들의 학번은 모두 1부터 N까지이다. 상근이의 학번은 1이다.

 

상근이는 동기들의 친구 관계를 모두 조사한 리스트를 가지고 있다. 이 리스트를 바탕으로 결혼식에 초대할 사람의 수를 구하는 프로그램을 작성하시오.

입력:

첫째 줄에 상근이의 동기의 수 n(2<=n<=500)이 주어진다. 둘째 줄에는 리스트의 길이 m(1<=m<=10000)이 주어진다. 다음 줄부터 m개 줄에는 친구 관계 ai,bi가 주어진다. (1<=ai<bi<=n) ai와 bi가 친구라는 뜻이며, bi 와 ai도 친구관계이다.

출력:

첫째 줄에 상근이의 결혼식에 초대하는 동기의 수를 출력한다.

풀이방법:

우선 입력으로 받은 값들을 그래프 형식으로 정리를 하는 작업을 거친다. 이후 BFS 방식을 사용해서 level이 2까지 가는 친구들(친구의 친구)을 찾는다. 항상 시작은 1이므로 queue에 1을 넣고 BFS 탐색을 두번 한다. 그렇게 탐색을 마치고 1을 제거한 뒤에 배열의 길이를 출력하도록 한다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
n=int(input())
m=int(input())
friends=[[]for i in range(n+1)]
for i in range(m):
    a,b=map(int,input().split())
    friends[a].append(b)
    friends[b].append(a)
 
answers=[]
queue=[1]
count=1
while len(queue):
    temp=[]
    for i in queue[:]:
        for j in friends[i]:
            if j in answers or count > 2:
                continue
            else:
                answers.append(j)
                temp.append(j)
        queue.pop(0)
    queue=temp
    count+=1
answers.remove(1)
print(len(answers))
cs

 

문제링크:

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

728x90
반응형

'Algorithm > Python' 카테고리의 다른 글

[BOJ]7576. 토마토  (0) 2019.10.29
[BOJ]1049. 기타줄  (0) 2019.10.18
[BOJ]1159. 농구 경기  (1) 2019.10.16
[BOJ]1016. 제곱ㄴㄴ수  (0) 2019.10.15
[BOJ]2960. 에라토스테네스의 체  (0) 2019.10.14
728x90
반응형

문제:

풀이방법:

이전 입양 시각 구하기에는 테이블에 있는 시간만 해도 상관이 없었으나 이번에는 전체 시간대를 표현해야 한다. 따라서 테이블에 없는 시간들을 만들어 줘야 한다. 그래서 시간 정보를 가지고 있는 새로운 테이블을 만들어서 이와 조인해서 표현하도록 한다.

1
2
3
4
5
6
7
8
9
10
11
12
13
-- 코드를 입력하세요
SELECT H1.HOUR, IFNULL(H2.COUNT, 0)
FROM (
    SELECT 0 as HOUR
    UNION SELECT 1 UNION SELECT 2 UNION SELECT 3 UNION SELECT 4 UNION SELECT 5 
    UNION SELECT 6 UNION SELECT 7 UNION SELECT 8 UNION SELECT 9 UNION SELECT 10
    UNION SELECT 11 UNION SELECT 12 UNION SELECT 13 UNION SELECT 14 UNION SELECT 15
    UNION SELECT 15 UNION SELECT 16 UNION SELECT 17 UNION SELECT 18 UNION SELECT 19
    UNION SELECT 20 UNION SELECT 21 UNION SELECT 22 UNION SELECT 23) H1
LEFT JOIN (
    SELECT HOUR(DATETIME) AS 'HOUR', COUNT(*) AS 'count'
    FROM ANIMAL_OUTS
    GROUP BY HOUR) as H2 on H1.hour = H2.hour ORDER BY H1.HOUR;
cs

문제링크:

https://programmers.co.kr/learn/courses/30/lessons/59413

728x90
반응형
728x90
반응형

문제:

상근이는 농구의 세계에서 점차 영향력을 넓혀가고 있다. 처음에 그는 농구 경기를 좋아하는 사람이었다. 농구에 대한 열정은 그를 막을 수 없었고, 결국 상근이는 농구장을 청소하는 일을 시작했다. 상근이도 농구장을 청소하면서 감독이 되기 위해 가져야할 능력을 공부해나갔다. 서당개 3년이면 풍월을 읊듯이 상근이는 점점 감독으로 한 걸음 다가가고 있었다. 어느 날 그에게 지방의 한 프로농구팀을 감독할 기회가 생기게 되었다. 그는 엄청난 지도력을 보여주며 프로 리그에서 우승을 했고, 이제 국가대표팀의 감독이 되었다.

 

내일은 일본과 국가대표 친선 경기가 있는 날이다. 상근이는 내일 경기에 나설 선발 명단을 작성해야 한다.

 

국가대표팀의 감독이 된 이후에 상근이는 매우 게을러졌다. 그는 선수의 이름을 기억하지 못하고, 각 선수의 능력도 알지 못한다. 따라서, 누가 선발인지 기억하기 쉽게 하기 위해 성의 첫 글자가 같은 선수 5명을 선발하려고 한다. 만약, 성의 첫 글자가 같은 선수가 5명보다 적다면, 상근이는 내일 있을 친성 경기를 기권하려고 한다.

 

상근이는 내일 경기를 위해 뽑을 수 있는 성의 첫 글자를 모두 구해보려고 한다.

입력:

첫째 줄에 선수의 수 N(1<=N<=150)이 주어진다. 다음 N개 줄에는 각 선수의 성이 주어진다. (성은 알파벳 소문자로만 이루어져 있고, 최대 30글자이다)

출력:

상근이가 선수 다섯 명을 선발할 수 없는 경우에는 "PREDAJA" (따옴표 없이)를 출력한다. PREDAJA는 크로아티아어로 항복을 의미한다. 선발할 수 있는 경우에는 가능한 성의 첫 글자를 사전순으로 공백없이 모두 출력한다.

풀이방법:

딕셔너리 자료형을 사용해서 해시 방법으로 풀었다. 맨 앞글자를 키로 하고 그에 따른 value는 나타낸 횟수로 지정했다. 이렇게 모든 이름을 다 한번씩 탐색해 딕셔너리로 정리를 마친다. 이를 items으로 가져와서 정렬한 뒤에 5이상인 값만 answer에 붙이도록한다. 만약 5이상인 값이 없었다면 answer는 빈 문자열일것이다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
n=int(input())
person=dict()
for i in range(n):
    inp=input()
    if inp[0in person:
        person[inp[0]]+=1
    else:
        person[inp[0]]=1
person=sorted(list(person.items()))
answer=''
for i,j in person:
    if j>=5:
        answer+=i
if answer=='':
    print("PREDAJA")
else:
    print(answer)
cs

문제링크:

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

728x90
반응형

'Algorithm > Python' 카테고리의 다른 글

[BOJ]1049. 기타줄  (0) 2019.10.18
[BOJ]5567. 결혼식  (0) 2019.10.17
[BOJ]1016. 제곱ㄴㄴ수  (0) 2019.10.15
[BOJ]2960. 에라토스테네스의 체  (0) 2019.10.14
[BOJ]2851. 슈퍼 마리오  (0) 2019.10.13
728x90
반응형

문제:

풀이방법:

NULL이 필요한 문제가 아니므로 기본 조인인 INNER JOIN을 사용해도 상관이 없다. 따라서 두 테이블을 INNER JOIN 했다. 그 다음에 보호 기간이 가장 길었다는 것은 O.DATETIME과 I.DATETIME의 차이가 크다는 것이다. 따라서 이 연산을 ORDER BY에다가 DESC 조건을 넣어서 찾도록 한다.

1
2
SELECT I.ANIMAL_ID, I.NAME FROM ANIMAL_INS I, ANIMAL_OUTS O WHERE I.ANIMAL_ID = O.ANIMAL_ID
ORDER BY (O.DATETIME -I.DATETIME) DESC LIMIT 2;
cs

문제링크:

https://programmers.co.kr/learn/courses/30/lessons/59411

728x90
반응형
728x90
반응형

문제:

어떤 수 X가 1보다 큰 제곱수로 나누어 떨어지지 않을 때, 제곱 ㄴㄴ수라고 한다. 제곱수는 정수의 제곱이다. min과 max가 주어지면, min과 max를 포함한 사이에 제곱 ㄴㄴ수가 몇 개 있는지 출력한다.

입력:

첫째 줄에 min과 max가 주어진다. min은 1보다 크거나 같고, 1,000,000,000,000보다 작거나 같은 자연수이고, max는 min보다 크거나 같고, min+1,000.000보다 작거나 같은 자연수이다.

출력:

첫째 줄에 [min,max]구간에 제곱ㄴㄴ 수가 몇 개인지 출력한다.

풀이방법:

어떤 수 X가 한 제곱수로 나누어지는지 확인하는 것 보다 제곱수가 나누어 떨어지게 만들 수 있는 수들을 지워나가는 것이 시간복잡도를 줄일 수 있다.(에라토스테네스의 체와 비슷)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
check=[0]*1000001
a,b=map(int,input().split())
for i in range(2,b):
    if i*> b:
        break
    start=i*i-a%(i*i)
    if start == i*i:
        start = 0
    for j in range(start,b-a+1,i*i):
        check[j]=1
ans=0
for i in range(b-a+1):
    if check[i]==0:
        ans+=1
print(ans)
cs

문제링크:

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

728x90
반응형

'Algorithm > Python' 카테고리의 다른 글

[BOJ]5567. 결혼식  (0) 2019.10.17
[BOJ]1159. 농구 경기  (1) 2019.10.16
[BOJ]2960. 에라토스테네스의 체  (0) 2019.10.14
[BOJ]2851. 슈퍼 마리오  (0) 2019.10.13
[BOJ]17144. 미세먼지 안녕!  (0) 2019.10.12
728x90
반응형

문제:

풀이방법:

조인을 통해서 NULL 값을 만들어야 한다면 LEFT JOIN이나 RIGHT JOIN을 써야 하는 것 같다. 따라서 '입양을 못 갔다' 라는 것은 INS에는 있지만 OUTS에는 없어야 하는 값들이다. 따라서 INS에 OUTS에 붙임으로써 입양을 못 간 동물들을 만들어 낸다. 이는 WHERE절로 O.ANIMAL_ID가 NULL인 값으로 찾을 수 있다. 그리고 3마리만 출력을 해야 하므로 LIMIT 3을 사용한다.

1
2
3
SELECT I.NAME,I.DATETIME FROM ANIMAL_INS I LEFT JOIN ANIMAL_OUTS O ON I.ANIMAL_ID=O.ANIMAL_ID
WHERE O.ANIMAL_ID is NULL
ORDER BY I.DATETIME LIMIT 3;
cs

문제링크:

https://programmers.co.kr/learn/courses/30/lessons/59044

728x90
반응형

+ Recent posts