728x90
반응형

문제:

수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다.

수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오.

입력:

첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어진다. N과 K는 정수이다.

출력:

첫째 줄에 수빈이가 동생을 찾는 가장 빠른 시간을 출력한다.

둘째 줄에 어떻게 이동해야 하는지 공백으로 구분해 출력한다.

풀이방법:

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

 

12851번: 숨바꼭질 2

수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때

www.acmicpc.net

 

2022.08.09 - [Algorithm/Python] - [BOJ]12851. 숨바꼭질 2

 이전 문제의 발전된 버전으로 가장 빠른 시간과 그 시간으로 이동한 경로를 출력해야 하는 문제다. 위 문제 해결 방법에 추가적으로 visited 배열을 이전에는 0과 1의 여부로만 사용했지만 count 값을 저장하도록 하여 최소 시간을 측정할 수 있도록 했다. 그리고 path라는 배열을 사용해서 이동한 점의 위치에 기존에 있었던 점의 값을 저장하도록 하여, 동생이 위치한 점에 도달했을 때, 역추론이 가능하도록 한다.

 역추론을 하기 위한 print_path라는 함수가 존재하며 history를 만든 후 이를 뒤집어서 출력하도록 한다.

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
from collections import deque
 
def print_path(now):
    history = []
    temp = now
    for _ in range(visited[now]+1):
        history.append(temp)
        temp = path[temp]
    print(" ".join(map(str, history[::-1])))
    
N, K = map(int,input().split())
visited = [0]*100001
path = [0]*100001
queue = deque([[N, 0]])
while queue:
    point, count = queue.popleft()
    if point==K:
        print(visited[point])
        print_path(point)
        break
    if point-1>=0 and not visited[point-1]:
        queue.append([point-1,count+1])
        visited[point-1]=count+1
        path[point-1] = point
    if point+1<=100000 and not visited[point+1]:
        queue.append([point+1,count+1])
        visited[point+1]=count+1
        path[point+1] = point
    if 2*point<=100000 and not visited[2*point]:
        queue.append([2*point,count+1])     
        visited[2*point]=count+1
        path[2*point] = point
 cs

문제링크:

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

 

13913번: 숨바꼭질 4

수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일

www.acmicpc.net

 

728x90
반응형
저작자표시 비영리 동일조건

'Algorithm' 카테고리의 다른 글

[BOJ]11559. Puyo Puyo  (0) 2021.09.07
[BOJ]3190. 뱀  (0) 2021.08.19
[BOJ]1520. 내리막길  (0) 2021.08.17
[BOJ]1987. 알파벳  (0) 2021.08.10
[BOJ]14425. 문자열 집합  (0) 2021.06.24
728x90
반응형

문제:

수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다.

수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 그리고, 가장 빠른 시간으로 찾는 방법이 몇 가지 인지 구하는 프로그램을 작성하시오.

입력:

첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어진다. N과 K는 정수이다.

출력:

첫째 줄에 수빈이가 동생을 찾는 가장 빠른 시간을 출력한다.

둘째 줄에는 가장 빠른 시간으로 수빈이가 동생을 찾는 방법의 수를 출력한다.

풀이방법:

BFS를 사용하여 수빈이가 이동할 수 있는 거리내에서 동생이 있는 위치에 도달하는 시간을 측정하도록 한다.

수빈이가 이동할 수 있는 방법은 총 3가지이므로, 이동할 점이 가능한 범위 내에 존재하고 이전에 도달한 적이 없는 곳이라면 queue에 넣고 이동하도록 한다. 그러다 동생이 있는 위치에 도달하면 해당 시간의 count를 하나 증가 시키고, 모든 탐색을 마친 뒤에는 시간, count의 dict에서 최소 시간의 count를 출력하도록 한다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
from collections import deque, defaultdict
N, K = map(int,input().split())
visited = [0]*100001
answer = defaultdict(int)
queue = deque([[N, 0]])
while queue:
    point, count = queue.popleft()
    visited[point]=1
    if point==K:
        answer[count]+=1
    if point-1>=0 and not visited[point-1]:
        queue.append([point-1,count+1])
    if point+1<=100000 and not visited[point+1]:
        queue.append([point+1,count+1])
    if 2*point<=100000 and not visited[2*point]:
        queue.append([2*point,count+1])     
 
answer = sorted(answer.items())
print(answer[0][0])
print(answer[0][1])
 cs

문제링크:

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

 

12851번: 숨바꼭질 2

수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때

www.acmicpc.net

 

728x90
반응형
저작자표시 비영리 동일조건

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

[BOJ]14620. 꽃길  (1) 2022.08.18
[BOJ]14497. 주난의 난(難)  (0) 2022.08.16
[BOJ]1189. 컴백홈  (0) 2022.08.04
[BOJ]12869.뮤탈리스크  (0) 2022.08.02
[BOJ]2852. NBA 농구  (0) 2022.07.28
728x90
반응형

문제:

한수는 캠프를 마치고 집에 돌아가려 한다. 한수는 현재 왼쪽 아래점에 있고 집은 오른쪽 위에 있다. 그리고 한수는 집에 돌아가는 방법이 다양하다. 단, 한수는 똑똑하여 한번 지나친 곳을 다시 방문하지는 않는다.

      cdef  ...f  ..ef  ..gh  cdeh  cdej  ...f 
      bT..  .T.e  .Td.  .Tfe  bTfg  bTfi  .Tde 
      a...  abcd  abc.  abcd  a...  a.gh  abc. 
거리 :  6     6     6     8     8    10    6

위 예제는 한수가 집에 돌아갈 수 있는 모든 경우를 나타낸 것이다. T로 표시된 부분은 가지 못하는 부분이다. 문제는 R x C 맵에 못가는 부분이 주어지고 거리 K가 주어지면 한수가 집까지도 도착하는 경우 중 거리가 K인 가짓수를 구하는 것이다.

입력:

첫 줄에 정수 R(1 ≤ R ≤ 5), C(1 ≤ C ≤ 5), K(1 ≤ K ≤ R×C)가 공백으로 구분되어 주어진다. 두 번째부터 R+1번째 줄까지는 R×C 맵의 정보를 나타내는 '.'과 'T'로 구성된 길이가 C인 문자열이 주어진다.

출력:

첫 줄에 거리가 K인 가짓수를 출력한다.

풀이방법:

 DFS를 사용해서 시작점에서 도착점까지 이동하고, 한 번의 이동마다 거리를 하나씩 늘린다. 도착점에 도달한 경우 거리가 K와 같다면 answer를 하나 증가시키고, 그렇지 않다면 다시 되돌아 오는 과정을 수행한다. '다시 되돌아 온다' 라는 행동을 하기 위해 visited 배열을 사용하고, 그 위치로 이동한 경우에는 해당 좌표의 값을 1로 바꾸고, 다시 되돌아 온 경우에는 0으로 다시 바꿔주도록 한다.

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
dx = [-1, 0 , 1, 0]
dy = [0, -1, 0 , 1]
 
from collections import deque
 
def dfs(x, y, count):
    global answer
    visited[x][y]=1
    if [x,y]==[0, C-1]:
        if count==K:
            answer+=1
        return
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if 0<= nx < R and 0 <= ny < C  and visited[nx][ny]==0 and maps[nx][ny]!='T':
            visited[nx][ny]=1
            dfs(nx,ny,count+1)
            visited[nx][ny]=0
            
R, C, K = map(int,input().split())
maps = [list(input()) for _ in range(R)]
visited = [[0 for _ in range(C)] for _ in range(R)]
answer= 0
dfs(R-1, 0, 1)
print(answer)
 cs

문제링크:

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

 

1189번: 컴백홈

첫 줄에 정수 R(1 ≤ R ≤ 5), C(1 ≤ C ≤ 5), K(1 ≤ K ≤ R×C)가 공백으로 구분되어 주어진다. 두 번째부터 R+1번째 줄까지는 R×C 맵의 정보를 나타내는 '.'과 'T'로 구성된 길이가 C인 문자열이 주어진다

www.acmicpc.net

 

728x90
반응형
저작자표시 비영리 동일조건

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

[BOJ]14497. 주난의 난(難)  (0) 2022.08.16
[BOJ]12851. 숨바꼭질 2  (0) 2022.08.09
[BOJ]12869.뮤탈리스크  (0) 2022.08.02
[BOJ]2852. NBA 농구  (0) 2022.07.28
[BOJ]3474. 교수가 된 현우  (0) 2022.07.26
728x90
반응형

문제:

수빈이는 강호와 함께 스타크래프트 게임을 하고 있다. 수빈이는 뮤탈리스크 1개가 남아있고, 강호는 SCV N개가 남아있다.

각각의 SCV는 남아있는 체력이 주어져있으며, 뮤탈리스크를 공격할 수는 없다. 즉, 이 게임은 수빈이가 이겼다는 것이다.

뮤탈리스크가 공격을 할 때, 한 번에 세 개의 SCV를 공격할 수 있다.

  1. 첫 번째로 공격받는 SCV는 체력 9를 잃는다.
  2. 두 번째로 공격받는 SCV는 체력 3을 잃는다.
  3. 세 번째로 공격받는 SCV는 체력 1을 잃는다.

SCV의 체력이 0 또는 그 이하가 되어버리면, SCV는 그 즉시 파괴된다. 한 번의 공격에서 같은 SCV를 여러 번 공격할 수는 없다.

남아있는 SCV의 체력이 주어졌을 때, 모든 SCV를 파괴하기 위해 공격해야 하는 횟수의 최솟값을 구하는 프로그램을 작성하시오.

입력:

첫째 줄에 SCV의 수 N (1 ≤ N ≤ 3)이 주어진다. 둘째 줄에는 SCV N개의 체력이 주어진다. 체력은 60보다 작거나 같은 자연수이다.

출력:

첫째 줄에 모든 SCV를 파괴하기 위한 공격 횟수의 최솟값을 출력한다.

풀이방법:

 SCV는 최대 3개까지만 있을 수 있기 때문에 이보다 더 적은 SCV가 들어온다면 0 배열을 이어 붙여서 길이가 3인 배열로 만들어 주도록 한다. SCV는 최대 체력이 60이고, 몇번째로 공격받느냐에 따라 체력이 달라지기 때문에 60의 길이를 가지는 3차원 visited 배열을 만든다.

 이후로는 BFS를 사용하여 나올 수 있는 경우의 수를 기반으로 체력을 감소시키며 모두 0이 되는 순간이 정답이다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
from itertools import permutations
from collections import deque
def bfs():
    q = deque([[scv, 0]])
    
    while q:
        state, count = q.popleft()
        if len(list(filter(lambda x: x>0, state)))==0:            
            break
        for attack in attacks:
            next_state = [0]*3
            for i in range(3):
                next_state[i] = max(0, state[i]-attack[i])
            if not visited[next_state[0]][next_state[1]][next_state[2]]:
                visited[next_state[0]][next_state[1]][next_state[2]] = 1
                q.append([next_state, count+1])
    return count
        
N = int(input())
scv = list(map(int,input().split()))+[0]*(3-N)
visited = [[[0 for _ in range(61)]for _ in range(61)]for _ in range(61)]
attacks = list(permutations([9,3,1],3))
print(bfs())
 cs

문제링크:

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

 

12869번: 뮤탈리스크

1, 3, 2 순서대로 공격을 하면, 남은 체력은 (12-9, 10-1, 4-3) = (3, 9, 1)이다. 2, 1, 3 순서대로 공격을 하면, 남은 체력은 (0, 0, 0)이다.

www.acmicpc.net

 

728x90
반응형
저작자표시 비영리 동일조건

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

[BOJ]12851. 숨바꼭질 2  (0) 2022.08.09
[BOJ]1189. 컴백홈  (0) 2022.08.04
[BOJ]2852. NBA 농구  (0) 2022.07.28
[BOJ]3474. 교수가 된 현우  (0) 2022.07.26
[BOJ]10709. 기상캐스터  (0) 2022.07.21
728x90
반응형

문제:

동혁이는 NBA 농구 경기를 즐겨 본다. 동혁이는 골이 들어갈 때 마다 골이 들어간 시간과 팀을 적는 이상한 취미를 가지고 있다.

농구 경기는 정확히 48분동안 진행된다. 각 팀이 몇 분동안 이기고 있었는지 출력하는 프로그램을 작성하시오.

입력:

첫째 줄에 골이 들어간 횟수 N(1<=N<=100)이 주어진다. 둘째 줄부터 N개의 줄에 득점 정보가 주어진다. 득점 정보는 득점한 팀의 번호와 득점한 시간으로 이루어져 있다. 팀 번호는 1 또는 2이다. 득점한 시간은 MM:SS(분:초) 형식이며, 분과 초가 한자리 일 경우 첫째자리가 0이다. 분은 0보다 크거나 같고, 47보다 작거나 같으며, 초는 0보다 크거나 같고, 59보다 작거나 같다. 득점 시간이 겹치는 경우는 없다.

출력:

첫째 줄에 1번 팀이 이기고 있던 시간, 둘째 줄에 2번 팀이 이기고 있던 시간을 출력한다. 시간은 입력과 같은 형식(MM:SS)으로 출력한다.

풀이방법:

 1번팀과 2번팀과의 점수를 기록하면서 한 팀이 점수를 앞서 나가는 순간에만 시간 차이를 계산하여 각 팀의 시간에 더해주도록 한다. 시간을 더할 때 계산의 편의성을 위해 초 단위로 모두 변환한다.

 중간중간 동점이 되는 경우도 있기 때문에 동점이 되기 전에 시간 차이를 더해준 뒤에 기준이 되는 시간을 갱신하고 각 팀에 점수를 더해주도록 한다.

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
N = int(input())
timeline = []
for _ in range(N):
    timeline.append(input().split())
timeline = sorted(timeline, key=lambda x: x[1])
timeline.append([-1, '48:00'])
one, two = 0, 0
pivot = ''
one_ans, two_ans = 0, 0
for team, time in timeline:
    if one==two:
        pass
    elif one>two:
        min_, sec = map(int,time.split(":"))
        min_p, sec_p = map(int, pivot.split(":"))
        one_ans += (min_*60+sec)-(min_p*60+sec_p)
    else:
        min_, sec = map(int,time.split(":"))
        min_p, sec_p = map(int, pivot.split(":"))
        two_ans += (min_*60+sec)-(min_p*60+sec_p)
    pivot = time
    if int(team)==1:
        one+=1
    elif int(team)==2:
        two+=1
q, r = divmod(one_ans, 60)
print(str(q).zfill(2)+":"+str(r).zfill(2))
q, r = divmod(two_ans, 60)
print(str(q).zfill(2)+":"+str(r).zfill(2))
 cs

문제링크:

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

 

2852번: NBA 농구

첫째 줄에 골이 들어간 횟수 N(1<=N<=100)이 주어진다. 둘째 줄부터 N개의 줄에 득점 정보가 주어진다. 득점 정보는 득점한 팀의 번호와 득점한 시간으로 이루어져 있다. 팀 번호는 1 또는 2이다. 득

www.acmicpc.net

 

728x90
반응형
저작자표시 비영리 동일조건

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

[BOJ]1189. 컴백홈  (0) 2022.08.04
[BOJ]12869.뮤탈리스크  (0) 2022.08.02
[BOJ]3474. 교수가 된 현우  (0) 2022.07.26
[BOJ]10709. 기상캐스터  (0) 2022.07.21
[BOJ]2870. 수학숙제  (0) 2022.07.19
728x90
반응형

문제:

알고리즘의 킹갓제너럴엠퍼러마제스티충무공알고리즘마스터 현우가 교수로 취임하였다!

그러나 학생들에게 크나큰 기대를 품고 첫 수업에 들어갔던 현우는 아무도 외판원 순회 문제(Traveling Salesman Problem, TSP)를 풀지 못하는 것을 보고 낙심하였다.

그 와중에 학생 남규는 TSP를 완전탐색으로 풀려고 하였고, 현우는 그걸 보고 경악을 금치 못한다. 왜냐면 TSP를 완전탐색으로 풀려면 O(N!)의 시간이 소모되는데, 이는 경악을 금치 못할 시간이기 때문이다.

그러나 남규는 O(N!)이 왜 큰지도 잘 모른다. 그래서 현우는 더더욱 경악을 금치 못하고, N!이 얼마나 큰지 대략적으로나마 알려주기 위해, 자연수 N이 주어지면 N!의 오른쪽 끝에 있는 0의 개수를 알려주기로 하였다.

그러나 현우는 경악을 금치 못하여 지금 코딩을 할 수 없는 상황이다. 여러분이 현우를 대신하여 프로그램을 작성하시오.

입력:

첫째 줄에 테스트 케이스의 개수 T가 주어지고, 이어서 T개의 줄에 정수 N이 주어진다(1 <= N <= 1000000000).

출력:

각 줄마다 N!의 오른쪽 끝에 있는 0의 개수를 출력한다.

풀이방법:

 오른쪽 끝에 0이 생기기 위해서는 2x5가 곱해져야 한다. 즉, N!을 소인수 분해 했을 때, 2와 5 중 더 작은 인수가 0의 갯수가 될 것이다. (2^P, 5^Q 일 때 P, Q 중 더 작은 수) 하지만 10까지만 봤을 때에도 2의 갯수가 압도적으로 많기 때문에 5의 개수만 알면 바로 0의 갯수를 알 수 있다. 따라서 5의 인수를 구하도록 한다.

1
2
3
4
5
6
7
8
9
10
T = int(input())
for _ in range(T):
    n = int(input())
    five = 5
    ans = 0
    while five <= n:
        ans += n//five
        five *= 5
        
    print(ans)
 cs

문제링크:

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

 

3474번: 교수가 된 현우

첫째 줄에 테스트 케이스의 개수 T가 주어지고, 이어서 T개의 줄에 정수 N이 주어진다(1 <= N <= 1000000000).

www.acmicpc.net

 

728x90
반응형
저작자표시 비영리 동일조건

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

[BOJ]12869.뮤탈리스크  (0) 2022.08.02
[BOJ]2852. NBA 농구  (0) 2022.07.28
[BOJ]10709. 기상캐스터  (0) 2022.07.21
[BOJ]2870. 수학숙제  (0) 2022.07.19
[BOJ]11758. CCW  (0) 2022.07.14
728x90
반응형

문제:

JOI시는 남북방향이 H 킬로미터, 동서방향이 W 킬로미터인 직사각형 모양이다. JOI시는 가로와 세로의 길이가 1킬로미터인 H × W 개의 작은 구역들로 나뉘어 있다. 북쪽으로부터 i 번째, 서쪽으로부터 j 번째에 있는 구역을 (i, j) 로 표시한다.

각 구역의 하늘에는 구름이 있을 수도, 없을 수도 있다. 모든 구름은 1분이 지날 때마다 1킬로미터씩 동쪽으로 이동한다. 오늘은 날씨가 정말 좋기 때문에 JOI시의 외부에서 구름이 이동해 오는 경우는 없다.

지금 각 구역의 하늘에 구름이 있는지 없는지를 알고 있다. 기상청에서 일하고 있는 여러분은 각 구역에 대해서 지금부터 몇 분뒤 처음으로 하늘에 구름이 오는지를 예측하는 일을 맡았다.

각 구역에 대해서 지금부터 몇 분뒤 처음으로 하늘에 구름이 오는지를 구하여라.

입력:

입력은 1 + H 행으로 주어진다.

첫 번째 행에는 정수 H, W (1 ≦ H ≦ 100, 1 ≦ W ≦ 100) 가 공백을 사이에 주고 주어진다. 이것은 JOI시가 H × W 개의 작은 구역으로 나뉘어 있다는 것을 의미한다.

이어진 H 개의 행의 i번째 행 (1 ≦ i ≦ H) 에는 W문자의 문자열이 주어진다. W 개의 문자 중 j번째 문자 (1 ≦ j ≦ W) 는, 구역 (i, j) 에 지금 구름이 떠 있는지 아닌지를 나타낸다. 구름이 있는 경우에는 영어 소문자 'c' 가, 구름이 없는 경우에는 문자 '.' 가 주어진다.

출력:

출력은 H 행으로, 각 행에는 공백으로 구분된 W 개의 정수를 출력한다. 출력의 i 번째 행 j 번째 정수 (1 ≦ i ≦ H, 1 ≦ j ≦ W) 는, 지금부터 몇 분후에 처음으로 구역 (i, j) 에 구름이 뜨는지를 표시한다. 단, 처음부터 구역 (i, j) 에 구름이 떠 있었던 경우에는 0을, 몇 분이 지나도 구름이 뜨지 않을 경우에는 -1을 출력한다.

풀이방법:

주어진 조건대로 구현해야 하는 문제다. 이 문제에서는 총 3가지 행동을 수행한다.

1. 지금 하늘에 구름(c)가 있는가?

2. 구름이 몇 분뒤에 지금 하늘에 도착하는가?

3. 구름의 이동

따라서 while 계속해서 반복하고, 1에 의해서 break 조건을 만든다. 그 동안에 2와 3을 반복하며 answer 2차원 배열을 채우도록 한다.

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
from collections import deque
 
def check_sky(sky):
    for i in range(H):
        for j in range(W):
            if sky[i][j]=='c':
                return 1
    return 0
 
def update_sky(sky, count):
    for i in range(H):
        for j in range(W):
            if sky[i][j]=='c':
                if answer[i][j]==-1:
                    answer[i][j] = count
 
H, W = map(int,input().split())
answer = [ [-1 for _ in range(W)] for _ in range(H)]
 
sky = []
for _ in range(H):
    sky.append(deque(input()))
    
count = 0
while True:
    if not check_sky(sky):
        break
    update_sky(sky, count)
    for i in range(H):
        sky[i].pop()
        sky[i].appendleft('.')
    count+=1
for ans in answer:
    print(*ans)
 cs

문제링크:

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

 

10709번: 기상캐스터

출력은 H 행으로, 각 행에는 공백으로 구분된 W 개의 정수를 출력한다. 출력의 i 번째 행 j 번째 정수 (1 ≦ i ≦ H, 1 ≦ j ≦ W) 는, 지금부터 몇 분후에 처음으로 구역 (i, j) 에 구름이 뜨는지를 표시

www.acmicpc.net

 

728x90
반응형
저작자표시 비영리 동일조건

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

[BOJ]2852. NBA 농구  (0) 2022.07.28
[BOJ]3474. 교수가 된 현우  (0) 2022.07.26
[BOJ]2870. 수학숙제  (0) 2022.07.19
[BOJ]11758. CCW  (0) 2022.07.14
[BOJ]4659. 비밀번호 발음하기  (0) 2022.07.12
728x90
반응형

문제:

상근이는 수학시간에 딴 짓을 하다가 선생님께 걸렸다. 선생님은 상근이에게 이번 주말동안 반성하라며 엄청난 숙제를 내주었다.

선생님이 상근이에게 준 종이에는 숫자와 알파벳 소문자로 되어있는 글자가 N줄있다. 상근이는 여기서 숫자를 모두 찾은 뒤, 이 숫자를 비내림차순으로 정리해야한다. 숫자의 앞에 0이 있는 경우에는 정리하면서 생략할 수 있다.

글자를 살펴보다가 숫자가 나오는 경우에는, 가능한 가장 큰 숫자를 찾아야 한다. 즉, 모든 숫자의 앞과 뒤에 문자가 있거나, 줄의 시작 또는 끝이어야 한다.

예를 들어, 01a2b3456cde478에서 숫자를 찾으면 1, 2, 3456, 478이다.

선생님이 준 종이의 내용이 주어졌을 때, 상근이의 숙제를 대신하는 프로그램을 작성하시오.

입력:

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

다음 N개의 줄에는 각 줄의 내용이 주어진다. 각 줄은 최대 100글자이고, 항상 알파벳 소문자와 숫자로만 이루어져 있다.

출력:

종이에서 찾은 숫자의 개수를 M이라고 하면, 출력은 M줄로 이루어져야 한다. 각 줄에는 종이에서 찾은 숫자를 하나씩 출력해야 한다. 이때, 비내림차순으로 출력해야 한다. 비내림차순은 내림차순의 반대인 경우인데, 다음 수가 앞의 수보다 크거나 같은 경우를 말한다.

풀이방법:

 python의 isdigit 기능을 사용해서 숫자를 찾도록 한다. 숫자가 연속해서 나오는 경우에는 이어붙이고, 숫자가 아닌 경우에만 배열에 담도록한다. 그리고 맨 끝의 숫자(lo3za4)에서 4도 탐색하기 위해서 for 문이 끝나고 나서 숫자가 남아있다면 추가로 넣어주도록한다.

 이렇게 모든 문자열 탐색이 끝난 뒤에, 배열에 있는 모든 숫자를 int형으로 바꾼 뒤에 정렬을 하도록 한다. (01과 같은 것을 제거하기 위함)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
N = int(input())
answer = []
for _ in range(N):
    line = input()
    number = ''
    for l in line:
        if l.isdigit():
            number+=l
        else:
            if len(number):
                answer.append(number)
            number=''
    if len(number):
        answer.append(number)
answer = sorted(list(map(int,answer)))
for ans in answer:
    print(ans)
 cs

문제링크:

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

 

2870번: 수학숙제

종이에서 찾은 숫자의 개수를 M이라고 하면, 출력은 M줄로 이루어져야 한다. 각 줄에는 종이에서 찾은 숫자를 하나씩 출력해야 한다. 이때, 비내림차순으로 출력해야 한다. 비내림차순은 내림차

www.acmicpc.net

 

728x90
반응형
저작자표시 비영리 동일조건

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

[BOJ]3474. 교수가 된 현우  (0) 2022.07.26
[BOJ]10709. 기상캐스터  (0) 2022.07.21
[BOJ]11758. CCW  (0) 2022.07.14
[BOJ]4659. 비밀번호 발음하기  (0) 2022.07.12
[BOJ]2910. 빈도 정렬  (0) 2022.06.30
728x90
반응형

문제:

2차원 좌표 평면 위에 있는 점 3개 P1, P2, P3가 주어진다. P1, P2, P3를 순서대로 이은 선분이 어떤 방향을 이루고 있는지 구하는 프로그램을 작성하시오.

입력:

첫째 줄에 P1의 (x1, y1), 둘째 줄에 P2의 (x2, y2), 셋째 줄에 P3의 (x3, y3)가 주어진다. (-10,000 ≤ x1, y1, x2, y2, x3, y3 ≤ 10,000) 모든 좌표는 정수이다. P1, P2, P3의 좌표는 서로 다르다.

출력:

P1, P2, P3를 순서대로 이은 선분이 반시계 방향을 나타내면 1, 시계 방향이면 -1, 일직선이면 0을 출력한다.

풀이방법:

 2차원 평면에서 점 3개의 방향을 판단하는 알고리즘을 CCW(Counter Clockwise)라고 한다. 외적을 사용하는 알고리즘인데, 아래 링크에서 자세하게 잘 설명해준 것 같아서 참조하도록 한다.

참고링크: https://degurii.tistory.com/47

1
2
3
4
5
6
7
8
9
10
px1, py1 = map(int,input().split())
px2, py2 = map(int,input().split())
px3, py3 = map(int,input().split())
D = (px2-px1)*(py3-py1)-(px3-px1)*(py2-py1)
if D > 0:
    print(1)
elif D==0:
    print(0)
else:
    print(-1)
 cs

문제링크:

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

 

11758번: CCW

첫째 줄에 P1의 (x1, y1), 둘째 줄에 P2의 (x2, y2), 셋째 줄에 P3의 (x3, y3)가 주어진다. (-10,000 ≤ x1, y1, x2, y2, x3, y3 ≤ 10,000) 모든 좌표는 정수이다. P1, P2, P3의 좌표는 서로 다르다.

www.acmicpc.net

 

728x90
반응형
저작자표시 비영리 동일조건

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

[BOJ]10709. 기상캐스터  (0) 2022.07.21
[BOJ]2870. 수학숙제  (0) 2022.07.19
[BOJ]4659. 비밀번호 발음하기  (0) 2022.07.12
[BOJ]2910. 빈도 정렬  (0) 2022.06.30
[BOJ]2828. 사과 담기 게임  (0) 2022.06.28
728x90
반응형

문제:

좋은 패스워드를 만드는것은 어려운 일이다. 대부분의 사용자들은 buddy처럼 발음하기 좋고 기억하기 쉬운 패스워드를 원하나, 이런 패스워드들은 보안의 문제가 발생한다. 어떤 사이트들은 xvtpzyo 같은 비밀번호를 무작위로 부여해 주기도 하지만, 사용자들은 이를 외우는데 어려움을 느끼고 심지어는 포스트잇에 적어 컴퓨터에 붙여놓는다. 가장 이상적인 해결법은 '발음이 가능한' 패스워드를 만드는 것으로 적당히 외우기 쉬우면서도 안전하게 계정을 지킬 수 있다.

회사 FnordCom은 그런 패스워드 생성기를 만들려고 계획중이다. 당신은 그 회사 품질 관리 부서의 직원으로 생성기를 테스트해보고 생성되는 패스워드의 품질을 평가하여야 한다. 높은 품질을 가진 비밀번호의 조건은 다음과 같다.

  1. 모음(a,e,i,o,u) 하나를 반드시 포함하여야 한다.
  2. 모음이 3개 혹은 자음이 3개 연속으로 오면 안 된다.
  3. 같은 글자가 연속적으로 두번 오면 안되나, ee 와 oo는 허용한다.

이 규칙은 완벽하지 않다;우리에게 친숙하거나 발음이 쉬운 단어 중에서도 품질이 낮게 평가되는 경우가 많이 있다.

입력:

입력은 여러개의 테스트 케이스로 이루어져 있다.

각 테스트 케이스는 한 줄로 이루어져 있으며, 각 줄에 테스트할 패스워드가 주어진다.

마지막 테스트 케이스는 end이며, 패스워드는 한글자 이상 20글자 이하의 문자열이다. 또한 패스워드는 대문자를 포함하지 않는다.

출력:

각 테스트 케이스를 '예제 출력'의 형태에 기반하여 품질을 평가하여라.

풀이방법:

이 문제에는 조건이 3개 있고, 각각 다음과 같이 처리하도록 한다.

 

1. 모음 하나를 반드시 포함하여야 한다.

vowel이라는 리스트를 선언하고, string의 chr 하나씩 보면서 모음인 경우에 vowel_check를 True로 변환해준다. 모든 string 탐색을 마친 뒤에 vowel_check를 확인하도록 한다.

 

2. 모음이 3개 혹은 자음이 3개 연속으로 오면 안 된다.

한 단어를 확인할 때마다. v, nv의 갯수를 업데이트 한다. 각각 vowel, non_vowel을 의미하고, 모음이 나온 경우에는 v++을 하고, nv는 0으로 만들어준다. 자음의 경우에는 반대로 수행한다. 그리고, 둘 중 하나가 3인 경우에는 answer를 False로 바꾼다.

 

3. 같은 글자가 연속적으로 두번 오면 안되나, ee와 oo는 허용한다.

각 chr를 stack에 담으면서 끝 값과 비교하도록 한다. 이 때 만약 같다는 조건문을 통과한 경우에는 answer를 False로 바꾸는데, ee와 oo만 따로 예외상황으로 빼도록 한다.

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
vowel = ['a','e','i','o','u']
while True:
    string = input()
    vowel_check=False
    if string=='end':
        break
    stack = []
    v = 0
    nv = 0
    answer= True
    for s in string:
        if s in vowel:
            vowel_check=True
            v+=1
            nv = 0
        else:
            nv+=1
            v= 0
        if nv==3 or v==3:
            answer =False
            break
        if len(stack):
            if stack[-1]==s:
                if s=='e' or s=='o':
                    continue
                answer = False
                break
            stack.append(s)
        else:
            stack.append(s)
            
    if answer and vowel_check:
        print(f"<{string}> is acceptable.")
    else:
        print(f"<{string}> is not acceptable.")
 cs

문제링크:

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

 

4659번: 비밀번호 발음하기

좋은 패스워드를 만드는것은 어려운 일이다. 대부분의 사용자들은 buddy처럼 발음하기 좋고 기억하기 쉬운 패스워드를 원하나, 이런 패스워드들은 보안의 문제가 발생한다. 어떤 사이트들은 xvtp

www.acmicpc.net

 

728x90
반응형
저작자표시 비영리 동일조건

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

[BOJ]2870. 수학숙제  (0) 2022.07.19
[BOJ]11758. CCW  (0) 2022.07.14
[BOJ]2910. 빈도 정렬  (0) 2022.06.30
[BOJ]2828. 사과 담기 게임  (0) 2022.06.28
[BOJ]3986. 좋은 단어  (0) 2022.06.23

+ Recent posts

티스토리툴바