투투

문제 단어 수학 문제는 N개의 단어로 이루어져 있으며 각 단어는 알파벳 대문자로만 이루어져있다. 이때 각 알파벳 대문자를 0부터 9까지의 숫자 중 하나로 바꿔서 N개의 수를 합한다. 이때 합이 최대가 되도록 만들어라. 입력 첫째 줄에 단어의 개수 N이 주어진다. 둘째 줄부터 N개의 줄에 단어가 한 줄에 하나씩 주어진다. 입력된 모든 단어에 포함되어 있는 알파벳은 최대 10개이며 수의 최대 길이는 8이다. 출력 첫째 줄에 최대값을 출력한다. 접근 처음에 접근했던 방식은 문자열의 길이가 큰 것의 앞자리부터 숫자를 매기는 것이었다. 하지만 어떻게 구현을 해야할지 감이 잡히지 않았다 그래서 구글링을 해본 결과 아래의 풀이가 흥미로웠다. suri78.tistory.com/183 [백준알고리즘] 1339번: 단어 ..

문제 길이가 64cm인 막대가 있다. 이 막대기를 잘르고 붙여서 Xcm인 막대를 만들려고한다. 막대를 자르는 가장 쉬운 방법은 절반으로 자르는 것이다. 막대는 다음과 같은 과정을 거쳐서 자른다. 1. 가지고있는 막대의 합이 X보다 크면 아래와 같은 과정을 반복한다. 1-1 가지고있는 막대 중 길이가 가장 짧은 것을 절반으로 자른다. 1-2 위에서 자른 막대 중 하나가 X보다 크거나 가타면 자른 것중 하나를 버린다. 2. 남아있는 모든 막대를 풀로붙여서 Xcm를 만든다. 몇 개의 막대로 Xcm를 만들 수 있는지 구하라. 입력 첫째 줄에 64이하의 자연수 X가 입력된다. 출력 Xcm 만들기위해 몇 개의 막대가 필요한지 출력한다. 비트연산자를 활용하는 방법을 공부하였다. 이를 어떻게 활용할 수 있을지 알고리즘..

문제 정육점에서 N개의 덩어리 중 무게 M만큼 사려고한다. 정육점은 이미 무게와 가격이 정해져있는데 어떤 덩어리를 샀을 때 그 덩어리보다 싼 고기들은 추가지불없이 얻을 수 있다. 정확히 M만큼의 무게가 되지 않는다면 그 이상을 살 수도 있다. 이때 M만큼의 고기를 사기위해 필요한 최소비용을 구하라 입력 첫째 줄에 N과 M이 주어진다. 이후 N개의 줄에 고기의 무게와 가격이 입력된다. 출력 최소비용을 출력하고 만약 구할 수 없다면 -1을 출력한다. 접근 가장 적은 비용으로 M의 고기를 사야한다. 고기의 무게와 가격이 입력되었을 때 가격은 오름차순으로 정렬, 무게는 내림차순으로 정렬한다. 즉 가장 싼 가격을 갖는 고기의 무게를 더해나간다. 왜냐하면 비싼 가격은 그 미만의 가격을 갖는 고기를 꽁짜로 얻을 수 ..

문제 어떠한 문장이 있을 때 괄호들이 균형이 잡혀있는지 검사한다. 소괄호는 소괄호끼리 대괄호는 대괄호끼리 짝을 이뤄야한다. 균형잡힌 문자열이라면 yes를 아니라면 no를 출력한다. 입력 여러 줄에 걸쳐서 문자열이 입력될 때 각 문자열이 균형이 잡혔는지 검사한다. 만약 "."이 들어온다면 문자 입력을 종료한다. 출력 각 문자열에 yes 또는 no를 출력한다. 접근 괄호에 대해 관심을 가져야한다. 균형이 잡혔다면 현재의 닫는괄호가 가장 최근에 나온 여는괄호와 짝이 맞아야한다. 스택은 가장 마지막에 넣은 데이터가 가장 위에 쌓이기 때문에 괄호를 스택에 넣어보도록 한다. 구현 기본적으로 while문안에서 실행이 된다. 괄호를 넣을 스택을 생성하고 string형의 input에 getline으로 문자열을 입력받는다..

문제 일직선 위에 N개의 높이가 서로 다른 탑을 왼쪽부터 세운다. 각 탑의 꼭대기에 송신기를 설치하였고 송신기는 일직선과 평행하게 왼쪽으로 발사한다. 그리고 모든 탑의 기둥에는 수신기가 설치되어있어서 다른 탑의 신호를 받을 수 있다. 이때 각 탑들이 신호를 보낼 때 몇 번째의 탑이 수신을 하는지 구하라. 6 9 5 7이라면 7은 9가, 5도 9가 수신을 하게된다. 입력 첫째 줄에 탑의 수를 나타내는 정수 N이 주어진다. (1이상 500,000이하) 두 번째 줄에 탑의 높이가 N개 주어진다. 출력 각 자리의 탑이 송신한 신호를 수신하는 탑의 위치를 출력한다. 접근 처음에 두 개의 FOR문으로 현재 탑을 기준으로 인덱스를 줄여가면서 왼쪽으로 탐색하도록 설계를 하였다. 하지만 시간초과가 발생하였는데 O(500..

import sys input = sys.stdin.readline N, K = map(int, input().split()) q = [n+1 for n in range(N)] answer = [] idx = 0 while q: idx = (idx + (K-1)) % len(q) answer.append(q.pop(idx)) print("".format(answer[-1])) 문제 1번부터 N번까지 N명의 사람이 원을 이루면서 앉아있고, 양의 정수 K가 주어진다. 이제 순서대로 K번째 사람을 제거할 때 제거되는 순서대로 출력하시오 입력 첫째 줄에 N과 K가 빈 칸을 사이에두고 순서대로 입력된다. 출력 안에 제거되는 순서대로 출력한다. 접근 처음에 사람들이 원모양으로 앉아있는 것을 어떻게 표현할까?라는 생..

문제 NxM의 격자에 토마토가 보관되어 있다. 토마토 중에는 잘 익은 토마토도 있고 아직 익지않은 토마토도 있다. 잘 익은 토마토는 익지않은 토마토에 영향을 주어 하루가 지나면 잘 익은 토마토 주위의 익지않은 토마토도 익게된다. 토마토의 주위는 상하좌우를 의미하며 상자의 일부 칸에는 토마토가 들어있지 않을 수도 있다. 이때 잘 익은 토마토에 의해 상자 안의 모든 토마토가 다 익으려면 며칠이 걸리는지 출력하라. 입력 첫째 줄에 상자의 크기 M, N이 주어진다. (2이상 1000이하) 둘째 줄부터 상자 안의 토마토에 대한 정보가 들어있으며 1은 잘 익은 토마토, 0은 익지 않은 토마토, -1은 토마토가 들어있지 않다. 출력 모든 토마토가 익을 때까지의 최소 날짜를 출력하고 처음부터 모든 토마토가 익어있다면 ..

문제 NxM 크기의 배열로 표현되는 미로가 있다. 미로에서 1은 이동할 수 있는 칸, 0은 이동할 수 없는 칸이다. 이때 (1, 1)에서 출발하여 (N, M)으로 이동할 때 지나야 하는 최소의 칸 수를 구하라 한 칸에서 다른 칸으로 이동할 때는 서로 인접한 칸으로만 이동할 수 있다. 칸을 셀 때는 시작 위치와 도착 위치도 포함한다. 입력 첫째 줄에 두 정수 N, M을 입력한다. (2이상 100이하) 이후 정수의 정보를 입력한다. 출력 첫째 줄에 지나야 하는 최소의 칸 수를 출력한다. 접근 출발점에서 도착점까지 최소길이로 가야한다. 그래서 이동할 때마다 카운트를해서 최솟값을 비교하는 방법을 생각해봤지만 BFS로 길을 탐색하다가 한 번 지나간길은 이전에 밟아온 칸에 +1을 해주어 최종적으로 도착점의 수를 출..

문제 NxN의 맵에 각 칸에는 지역의 높이 정보가 담겨져있다. 장마철에 많은 비가 내려 높이가 4이하인 모든 지점에 물이 잠긴다고 하면 물에 잠기지 않은 지역 중 인접한 영역들을 안전영역이라 한다. 인접한 영역은 상하좌우를 기준으로 한다. 이때 이 지역에서 물에 잠기지 않는 안전한 영역의 최대 개수를 구하라. 입력 첫째 줄에 지역의 크기를 나타내는 N이 주어진다. (2이상 100이하) 이후 맵에 대한 정보가 입력되며 각각의 높이는 1이상 100이하이다. 출력 장마철에 물에 잠기지 않는 안전영역의 최대 개수를 출력한다. 접근 비의 양을 조절하면서 안전영역을 구해 최댓값을 비교해야 한다. 비의 양은 0부터 입력받은 높이 중 최대 높임만큼 온다고 설정한다. 그리고 이 범위 안에서 FOR문을 돌아 안전영역을 구..

문제 정사각형으로 이루어져 있는 섬과 바다 지도가 주어진다. 섬의 개수를 세어 출력해야는데 섬은 상하좌우, 대각선에 연결된 땅이 있으면 하나의 섬으로 본다. 입력 여러 개의 테스트 케이스로 이루어져 있고 0 0을 입력하면 종료된다. 각 테스트 케이스에서 첫째 줄에 지도의 너비W와 높이H가 입력된다. (너비와 높이는 1이상 50이하) 이어서 H개의 줄에 지도가 주어지며 1은 땅 0은 바다이다. 출력 각 테스트 케이스에 대해서 섬의 개수를 출력한다. 접근 어떤 땅이 있는 자리에서 상하좌우, 대각선에 땅이 위치하면 하나의 섬이다. 따라서 땅을 만났을 때 더이상 이동할 수 없을 때까지 탐색을 하여 섬을 파악한다. 이 문제에서 DFS를 실행한만큼 섬의 개수가 된다. 구현 while문을 통해 여러 개의 테스트 케이..