TIL #13 3.14 백준문제

백준문제 1316번 - 그룹단어 체커

문제

그룹 단어란 단어에 존재하는 모든 문자에 대해서, 각 문자가 연속해서 나타나는 경우만을 말한다. 예를 들면, ccazzzzbb는 c, a, z, b가 모두 연속해서 나타나고, kin도 k, i, n이 연속해서 나타나기 때문에 그룹 단어이지만, aabbbccb는 b가 떨어져서 나타나기 때문에 그룹 단어가 아니다.

단어 N개를 입력으로 받아 그룹 단어의 개수를 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 단어의 개수 N이 들어온다. N은 100보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 단어가 들어온다. 단어는 알파벳 소문자로만 되어있고 중복되지 않으며, 길이는 최대 100이다.

출력

첫째 줄에 그룹 단어의 개수를 출력한다.

풀이

#그룹단어 체커 -백준문제 (복습)
import sys
word_number = int(sys.stdin.readline())    
words_ = [sys.stdin.readline().lower() for _ in range(word_number)] #입력할 단어들을 list 형태로 받아내는 구조
count = 0

for word in words_: #리스트안에서 각 단어들 호출
    test_result = 0 #리스트의 단어가 바뀔때마다 test_result를 초기화
    for j in range(len(word)): 
        if word.find(word[j], j+1) - j > 1: #단어 알파벳들중 같은 알파벳을 찾는 방법. find()함수를 이용해서 찾아낸다. 해당 알파벳을 다음 위치부터 돌면서 같은 알파벳끼리의 거리가 1이상이면 return false
            test_result = -1
            break

        else:
            test_result =1 #모든 원소를 돌고 거리가 1이상인 알파벳 인덱스가 없을 경우 test_result = 1 반환 
    
    if test_result == 1:
        count += 1

    else:
        continue

print(count)

백준문제 2839번 - 설탕배달

문제

상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕공장에서 만드는 설탕은 봉지에 담겨져 있다. 봉지는 3킬로그램 봉지와 5킬로그램 봉지가 있다.

상근이는 귀찮기 때문에, 최대한 적은 봉지를 들고 가려고 한다. 예를 들어, 18킬로그램 설탕을 배달해야 할 때, 3킬로그램 봉지 6개를 가져가도 되지만, 5킬로그램 3개와 3킬로그램 1개를 배달하면, 더 적은 개수의 봉지를 배달할 수 있다.

상근이가 설탕을 정확하게 N킬로그램 배달해야 할 때, 봉지 몇 개를 가져가면 되는지 그 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N이 주어진다. (3 ≤ N ≤ 5000)

출력

상근이가 배달하는 봉지의 최소 개수를 출력한다. 만약, 정확하게 N킬로그램을 만들 수 없다면 -1을 출력한다.

풀이:

import sys
N = int(sys.stdin.readline())

if N % 5 == 0:     #5로 나누어진다면 바로 5로 나누어진 몫이 정답이다.
    print(N//5)

else:
    threekg_bag = 1  #처음에 3kg짜리 가방을 1개로 대입하고 시작한다
    min_list = []  #최소한의 갯수를 구하기위해서 쓰일 리스트

    while N>=3:  #무조건 3이상인경우면 가능 3키로이상부터 3kg 가방에 넣을 수 있다.
        N -=3
        if N % 5 == 0:  #3을 처음에 빼고 5로 나누어지면 3kg짜리 가방갯수 + N을 5로나눈 몫을 더한고 list에 append
            min_list.append(threekg_bag + N//5)
        else:
            threekg_bag +=1

    if len(min_list) == 0: #min_list에 아무것도 없으면 나누어지지 않는 숫자이기에 -1반환
        print(-1)

    else:
        print(min(min_list))

백준문제 1011번 - Fly me to the Centuari

문제

우현이는 어린 시절, 지구 외의 다른 행성에서도 인류들이 살아갈 수 있는 미래가 오리라 믿었다. 그리고 그가 지구라는 세상에 발을 내려 놓은 지 23년이 지난 지금, 세계 최연소 ASNA 우주 비행사가 되어 새로운 세계에 발을 내려 놓는 영광의 순간을 기다리고 있다.

그가 탑승하게 될 우주선은 Alpha Centauri라는 새로운 인류의 보금자리를 개척하기 위한 대규모 생활 유지 시스템을 탑재하고 있기 때문에, 그 크기와 질량이 엄청난 이유로 최신기술력을 총 동원하여 개발한 공간이동 장치를 탑재하였다. 하지만 이 공간이동 장치는 이동 거리를 급격하게 늘릴 경우 기계에 심각한 결함이 발생하는 단점이 있어서, 이전 작동시기에 k광년을 이동하였을 때는 k-1 , k 혹은 k+1 광년만을 다시 이동할 수 있다. 예를 들어, 이 장치를 처음 작동시킬 경우 -1 , 0 , 1 광년을 이론상 이동할 수 있으나 사실상 음수 혹은 0 거리만큼의 이동은 의미가 없으므로 1 광년을 이동할 수 있으며, 그 다음에는 0 , 1 , 2 광년을 이동할 수 있는 것이다. ( 여기서 다시 2광년을 이동한다면 다음 시기엔 1, 2, 3 광년을 이동할 수 있다. )

김우현은 공간이동 장치 작동시의 에너지 소모가 크다는 점을 잘 알고 있기 때문에 x지점에서 y지점을 향해 최소한의 작동 횟수로 이동하려 한다. 하지만 y지점에 도착해서도 공간 이동장치의 안전성을 위하여 y지점에 도착하기 바로 직전의 이동거리는 반드시 1광년으로 하려 한다.

김우현을 위해 x지점부터 정확히 y지점으로 이동하는데 필요한 공간 이동 장치 작동 횟수의 최솟값을 구하는 프로그램을 작성하라.

입력

입력의 첫 줄에는 테스트케이스의 개수 T가 주어진다. 각각의 테스트 케이스에 대해 현재 위치 x 와 목표 위치 y 가 정수로 주어지며, x는 항상 y보다 작은 값을 갖는다. (0 ≤ x < y < 231)

출력

각 테스트 케이스에 대해 x지점으로부터 y지점까지 정확히 도달하는데 필요한 최소한의 공간이동 장치 작동 횟수를 출력한다.

풀이

import math
import sys
N = int(sys.stdin.readline())

for _ in range(N):
    x, y = map(int, sys.stdin.readline().split())
    distance = y -x    # 두 거리를 계산할 때 필요하다.
    count = 0 

    #해당문제는 거리의 제곱근 기준으로 최소 이동 횟수를 잡을 수 있다.
    trial_number = math.floor(math.sqrt(distance))  #거리의 제곱근을 구한다. 10이면 3과 4이인데 floor를 사용하여 3으로 반환
    trial_number_square = trial_number ** 2 #trial_number의 제곱수를 반환
    trial_plus_one = math.sqrt(trial_number_square) # 이동횟수를 +1해줄 최소 distance 움직임 수

    #거리에 따라서 나눈 구조
    if distance > trial_number_square + trial_plus_one:
        count = 2 * trial_number + 1
    elif distance > trial_number and distance <= trial_number_square + trial_plus_one:
        count = 2 * trial_number
    elif distance == trial_number_square:
        count = (2 * trial_number) -1
    elif distance < 4:
        count = distance

print(count)

문제

베르트랑 공준은 임의의 자연수 n에 대하여, n보다 크고, 2n보다 작거나 같은 소수는 적어도 하나 존재한다는 내용을 담고 있다.

이 명제는 조제프 베르트랑이 1845년에 추측했고, 파프누티 체비쇼프가 1850년에 증명했다.

예를 들어, 10보다 크고, 20보다 작거나 같은 소수는 4개가 있다. (11, 13, 17, 19) 또, 14보다 크고, 28보다 작거나 같은 소수는 3개가 있다. (17,19, 23)

자연수 n이 주어졌을 때, n보다 크고, 2n보다 작거나 같은 소수의 개수를 구하는 프로그램을 작성하시오.

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 케이스는 n을 포함하는 한 줄로 이루어져 있다.

입력의 마지막에는 0이 주어진다.

출력

각 테스트 케이스에 대해서, n보다 크고, 2n보다 작거나 같은 소수의 개수를 출력한다.

import sys

m = int(sys.stdin.readline())
n = 2*m + 1
prime_truth = [True] * n
prime_list = []


for i in range(2, int(n**0.5)+1):
    if prime_truth[i] == True:
        for j in range(2*i,n,i):
            prime_truth[j] == False
    

for i in range(m+1, n):
    if i > 1 and prime_truth[i] == True:
        prime_list.append(i)

print(len(prime_list))

문제

666은 종말을 나타내는 숫자라고 한다. 따라서, 많은 블록버스터 영화에서는 666이 들어간 제목을 많이 사용한다. 영화감독 숌은 세상의 종말 이라는 시리즈 영화의 감독이다. 조지 루카스는 스타워즈를 만들 때, 스타워즈 1, 스타워즈 2, 스타워즈 3, 스타워즈 4, 스타워즈 5, 스타워즈 6과 같이 이름을 지었고, 피터 잭슨은 반지의 제왕을 만들 때, 반지의 제왕 1, 반지의 제왕 2, 반지의 제왕 3과 같이 영화 제목을 지었다.

하지만 숌은 자신이 조지 루카스와 피터 잭슨을 뛰어넘는다는 것을 보여주기 위해서 영화 제목을 좀 다르게 만들기로 했다.

종말의 숫자란 어떤 수에 6이 적어도 3개이상 연속으로 들어가는 수를 말한다. 제일 작은 종말의 숫자는 666이고, 그 다음으로 큰 수는 1666, 2666, 3666, .... 과 같다.

따라서, 숌은 첫 번째 영화의 제목은 세상의 종말 666, 두 번째 영화의 제목은 세상의 종말 1666 이렇게 이름을 지을 것이다. 일반화해서 생각하면, N번째 영화의 제목은 세상의 종말 (N번째로 작은 종말의 숫자) 와 같다.

숌이 만든 N번째 영화의 제목에 들어간 숫자를 출력하는 프로그램을 작성하시오. 숌은 이 시리즈를 항상 차례대로 만들고, 다른 영화는 만들지 않는다.

입력

첫째 줄에 숫자 N이 주어진다. N은 10,000보다 작거나 같은 자연수이다.

출력

첫째 줄에 N번째 영화의 제목에 들어간 수를 출력한다.

import sys

Number = int(sys.stdin.readline())
k, cnt = 666, 0  # 카운트를 셀 변수와 꾸준히 증가해야하는 변수를 하나 지정해서 진행

while True:    
    if '666' in str(k): #'666'이라는 문자열이 k str에 있다면 cnt 하나 증가 - 첫번쨰 666은 첫번째 cnt 2번째 666은 두번째 cnt
        cnt += 1
    
    if cnt == Number: #count랑 입력한값이랑 같아졌을 때 계속 1씩 증가시키던 k값을 프린트하면 정답이 나온다.
        print(k)
        break

    else:
        k +=1