IT-garden

문제

상근이는 어렸을 적에 "봄보니 (Bomboni)" 게임을 즐겨했다.

가장 처음에 N×N크기에 사탕을 채워 놓는다. 사탕의 색은 모두 같지 않을 수도 있다. 상근이는 사탕의 색이 다른 인접한 두 칸을 고른다. 그 다음 고른 칸에 들어있는 사탕을 서로 교환한다. 이제, 모두 같은 색으로 이루어져 있는 가장 긴 연속 부분(행 또는 열)을 고른 다음 그 사탕을 모두 먹는다.

사탕이 채워진 상태가 주어졌을 때, 상근이가 먹을 수 있는 사탕의 최대 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 보드의 크기 N이 주어진다. (3 ≤ N ≤ 50)

다음 N개 줄에는 보드에 채워져 있는 사탕의 색상이 주어진다. 빨간색은 C, 파란색은 P, 초록색은 Z, 노란색은 Y로 주어진다.

사탕의 색이 다른 인접한 두 칸이 존재하는 입력만 주어진다.

출력

첫째 줄에 상근이가 먹을 수 있는 사탕의 최대 개수를 출력한다.

예제 입력과 출력

알고리즘 분류

브루트 포스 

정답

import sys
input= lambda : sys.stdin.readline().strip()

n=int(input())
a=[list(input()) for i in range(n)]
r=0

def width():
    global r
    
    for i in range(n):
        c=1  
        for j in range(1,n):
            if a[i][j] == a[i][j-1]:
                c += 1
            else:
                if r < c:
                    r=c
                c=1
                
        if r < c: # 한줄이 모두 같은 경우 처리
            r=c

def height():
    global r
    
    for i in range(n):
        c=1
        for j in range(1,n):
            if a[j][i] == a[j-1][i]:
                c += 1
            else:
                if r < c:
                    r=c
                c=1
                
        if r < c:
            r=c

for i in range(n):
    for j in range(1,n):
        a[i][j],a[i][j-1] = a[i][j-1], a[i][j] # 사탕 교환
        width()
        height() 
        a[i][j],a[i][j-1] = a[i][j-1], a[i][j] # 교환한 것을 원래대로

for i in range(n):
    for j in range(1,n):
        a[j][i],a[j-1][i] = a[j-1][i], a[j][i] # 사탕 교환
        width()
        height()
        a[j][i],a[j-1][i] = a[j-1][i], a[j][i] # 교환한 것을 원래대로

print(r)

1. 인접한 두 칸을 골라 사탕을 교환하고 전체 보드를 탐색하여 같은 색으로 이루어진 사탕 개수를 확인합니다.
2. 사탕의 최대 개수 r보다 구한 사탕 개수 c가 더 크면 r를 c로 바꿉니다.
3. 교환한 사탕을 원래대로 돌려 놓습니다.
4. 1, 2, 3의 과정을 사탕을 교환하는 모든 경우에 실행합니다.
5. 사탕의 최대 개수 r을 출력합니다.

백준 알고리즘 3085번 : https://www.acmicpc.net/problem/3085

문제

삼각수 Tn(n ≥ 1)는 [그림]에서와 같이 기하학적으로 일정한 모양의 규칙을 갖는 점들의 모음으로 표현될 수 있다.

자연수 n에 대해 n ≥ 1의 삼각수Tn는 명백한 공식이 있다.

Tn = 1 + 2 + 3 + ... + n = n(n+1)/2

1796년, 가우스는 모든 자연수가 최대 3개의 삼각수의 합으로 표현될 수 있다고 증명하였다. 예를 들어,

• 4 = T1 + T2
• 5 = T1 + T1 + T2
• 6 = T2 + T2 or 6 = T3
• 10 = T1 + T2 + T3 or 10 = T4

이 결과는 증명을 기념하기 위해 그의 다이어리에 “Eureka! num = Δ + Δ + Δ” 라고 적은것에서 유레카 이론으로 알려졌다. 꿍은 몇몇 자연수가 정확히 3개의 삼각수의 합으로 표현될 수 있는지 궁금해졌다. 위의 예시에서, 5와 10은 정확히 3개의 삼각수의 합으로 표현될 수 있지만 4와 6은 그렇지 않다.

자연수가 주어졌을 때, 그 정수가 정확히 3개의 삼각수의 합으로 표현될 수 있는지 없는지를 판단해주는 프로그램을 만들어라. 단, 3개의 삼각수가 모두 달라야 할 필요는 없다.

입력

프로그램은 표준입력을 사용한다. 테스트케이스의 개수는 입력의 첫 번째 줄에 주어진다. 각 테스트케이스는 한 줄에 자연수 K (3 ≤ K ≤ 1,000)가 하나씩 포함되어있는 T개의 라인으로 구성되어있다.

출력

프로그램은 표준출력을 사용한다. 각 테스트케이스에대해 정확히 한 라인을 출력한다. 만약 K가 정확히 3개의 삼각수의 합으로 표현될수 있다면 1을, 그렇지 않다면 0을 출력한다.

예제 입력과 출력

알고리즘 분류

브루트 포스 

정답

from itertools import combinations_with_replacement
import sys
input = lambda: sys.stdin.readline().strip()

n=int(input())
a=[int(input()) for i in range(n)]

for i in a:
    t=[]
    z=0
    
    for j in range(1,i+1):
        if (j*(j+1))//2 > i:
            break
        
        t.append((j*(j+1))//2)

    com=list(combinations_with_replacement(t,3))

    for k in com:
        if sum(k) == i:
            z=1
            break

    print(z)

입력받은 k에 대한 삼각수 공식을 만들어 리스트 t에 넣습니다.
리스트 t의 요소 중 3개를 뽑아 반복 가능한 조합을 만듭니다.
조합들의 합 중 k와 같은 값이 있으면 1을 출력하고 없으면 0을 출력합니다.

백준 알고리즘 10448번 : https://www.acmicpc.net/problem/10448

문제

준규가 사는 나라는 우리가 사용하는 연도와 다른 방식을 이용한다. 준규가 사는 나라에서는 수 3개를 이용해서 연도를 나타낸다. 각각의 수는 지구, 태양, 그리고 달을 나타낸다.

지구를 나타내는 수를 E, 태양을 나타내는 수를 S, 달을 나타내는 수를 M이라고 했을 때, 이 세 수는 서로 다른 범위를 가진다. (1 ≤ E ≤ 15, 1 ≤ S ≤ 28, 1 ≤ M ≤ 19)

우리가 알고있는 1년은 준규가 살고있는 나라에서는 1 1 1로 나타낼 수 있다. 1년이 지날 때마다, 세 수는 모두 1씩 증가한다. 만약, 어떤 수가 범위를 넘어가는 경우에는 1이 된다.

예를 들어, 15년은 15 15 15로 나타낼 수 있다. 하지만, 1년이 지나서 16년이 되면 16 16 16이 아니라 1 16 16이 된다. 이유는 1 ≤ E ≤ 15 라서 범위를 넘어가기 때문이다.

E, S, M이 주어졌고, 1년이 준규가 사는 나라에서 1 1 1일때, 준규가 사는 나라에서 E S M이 우리가 알고 있는 연도로 몇 년인지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 세 수 E, S, M이 주어진다. 문제에 나와있는 범위를 지키는 입력만 주어진다.

출력

첫째 줄에 E S M으로 표시되는 가장 빠른 연도를 출력한다. 1 1 1은 항상 1이기 때문에, 정답이 음수가 나오는 경우는 없다.

예제 입력과 출력

알고리즘 분류

수학
중국인의 나머지 정리

정답

e, s, m= map(int, input().split())
c=1

while True:
    if (c-e) % 15 == 0 and (c-s) % 28 == 0 and (c-m) % 19 == 0:
        print(c)
        break
    c += 1

백준 알고리즘 1476번 : https://www.acmicpc.net/problem/1476

문제

KOI 통신연구소는 레이저를 이용한 새로운 비밀 통신 시스템 개발을 위한 실험을 하고 있다. 실험을 위하여 일직선 위에 N개의 높이가 서로 다른 탑을 수평 직선의 왼쪽부터 오른쪽 방향으로 차례로 세우고, 각 탑의 꼭대기에 레이저 송신기를 설치하였다. 모든 탑의 레이저 송신기는 레이저 신호를 지표면과 평행하게 수평 직선의 왼쪽 방향으로 발사하고, 탑의 기둥 모두에는 레이저 신호를 수신하는 장치가 설치되어 있다. 하나의 탑에서 발사된 레이저 신호는 가장 먼저 만나는 단 하나의 탑에서만 수신이 가능하다.

예를 들어 높이가 6, 9, 5, 7, 4인 다섯 개의 탑이 수평 직선에 일렬로 서 있고, 모든 탑에서는 주어진 탑 순서의 반대 방향(왼쪽 방향)으로 동시에 레이저 신호를 발사한다고 하자. 그러면, 높이가 4인 다섯 번째 탑에서 발사한 레이저 신호는 높이가 7인 네 번째 탑이 수신을 하고, 높이가 7인 네 번째 탑의 신호는 높이가 9인 두 번째 탑이, 높이가 5인 세 번째 탑의 신호도 높이가 9인 두 번째 탑이 수신을 한다. 높이가 9인 두 번째 탑과 높이가 6인 첫 번째 탑이 보낸 레이저 신호는 어떤 탑에서도 수신을 하지 못한다.

탑들의 개수 N과 탑들의 높이가 주어질 때, 각각의 탑에서 발사한 레이저 신호를 어느 탑에서 수신하는지를 알아내는 프로그램을 작성하라.

입력

첫째 줄에 탑의 수를 나타내는 정수 N이 주어진다. N은 1 이상 500,000 이하이다. 둘째 줄에는 N개의 탑들의 높이가 직선상에 놓인 순서대로 하나의 빈칸을 사이에 두고 주어진다. 탑들의 높이는 1 이상 100,000,000 이하의 정수이다.

출력

첫째 줄에 주어진 탑들의 순서대로 각각의 탑들에서 발사한 레이저 신호를 수신한 탑들의 번호를 하나의 빈칸을 사이에 두고 출력한다. 만약 레이저 신호를 수신하는 탑이 존재하지 않으면 0을 출력한다.

예제 입력과 출력

알고리즘 분류

스택

정답

from collections import deque

n=int(input())
a=list(map(int,input().split()))
li=deque()
r=[]

for i in range(n):
    while li:
        if li[-1][1] > a[i]:
            r.append(li[-1][0] + 1)
            break
        li.pop()

    if not li:
        r.append(0)

    li.append([i, a[i]])
    
for i in range(n):
    print(r[i], end=' ')

백준 알고리즘 2493번 : https://www.acmicpc.net/problem/2493

문제

4개의 기호 ‘(’, ‘)’, ‘[’, ‘]’를 이용해서 만들어지는 괄호열 중에서 올바른 괄호열이란 다음과 같이 정의된다.

1. 한 쌍의 괄호로만 이루어진 ‘()’와 ‘[]’는 올바른 괄호열이다.
2. 만일 X가 올바른 괄호열이면 ‘(X)’이나 ‘[X]’도 모두 올바른 괄호열이 된다.
3. X와 Y 모두 올바른 괄호열이라면 이들을 결합한 XY도 올바른 괄호열이 된다.

예를 들어 ‘(()[[]])’나 ‘(())[][]’ 는 올바른 괄호열이지만 ‘([)]’ 나 ‘(()()[]’ 은 모두 올바른 괄호열이 아니다. 우리는 어떤 올바른 괄호열 X에 대하여 그 괄호열의 값(괄호값)을 아래와 같이 정의하고 값(X)로 표시한다.

1. ‘()’ 인 괄호열의 값은 2이다.
2. ‘[]’ 인 괄호열의 값은 3이다.
3. ‘(X)’ 의 괄호값은 2×값(X) 으로 계산된다.
4. ‘[X]’ 의 괄호값은 3×값(X) 으로 계산된다.
5. 올바른 괄호열 X와 Y가 결합된 XY의 괄호값은 값(XY)= 값(X)+값(Y) 로 계산된다.

예를 들어 ‘(()[[]])([])’ 의 괄호값을 구해보자. ‘()[[]]’ 의 괄호값이 2 + 3×3=11 이므로 ‘(()[[ ]])’의 괄호값은 2×11=22 이다. 그리고 ‘([])’의 값은 2×3=6 이므로 전체 괄호열의 값은 22 + 6 = 28 이다.

여러분이 풀어야 할 문제는 주어진 괄호열을 읽고 그 괄호값을 앞에서 정의한대로 계산하여 출력하는 것이다.

입력

첫째 줄에 괄호열을 나타내는 문자열(스트링)이 주어진다. 단 그 길이는 1 이상, 30 이하이다.

출력

첫째 줄에 그 괄호열의 값을 나타내는 정수를 출력한다. 만일 입력이 올바르지 못한 괄호열이면 반드시 0을 출력해야 한다. 

예제 입력과 출력

알고리즘 분류

스택

정답

s = list(input())
stack = []
c = 0

for i in s:
    if i == ')':
        t = 0
        while len(stack) != 0:
            top = stack.pop()
            if top == '(':
                if t == 0:
                    stack.append(2)
                else:
                    stack.append(2 * t)
                break
            elif top == '[':
                print(0)
                exit(0)
            else:
                t = t + int(top)
 
    elif i == ']':
        t = 0
        while len(stack) != 0:
            top = stack.pop()
            if top == '[':
                if t == 0:
                    stack.append(3)
                else:
                    stack.append(3 * t)
                break
            elif top == '(':
                print(0)
                exit(0)
            else:
                t = t + int(top)
 
    else:
        stack.append(i)
 
for i in stack:
    if i == '(' or i == '[':
        print(0)
        exit(0)
    else:
        c += i
 
print(c)

1. '('와 '[' 가 들어오면 스택에 넣습니다.
2. ')'와 ']'인 경우를 나눠 생각합니다.
3. 각 경우 스택이 1 이상인 경우 스택의 맨 위 요소를 뽑아 '('나 '['인지 확인합니다.
바로 맨 위가 '('나 '['이면 2나 3을 넣고 앞에 숫자들이 있는 경우 그 숫자들의 합을 구해 합에 2나 3을 곱합니다.
4. 각 경우 짝이 맞지 않는 괄호가 오면 0을 출력하고 프로그램을 종료합니다.
5. 문자열에 대한 for문이 끝나고 괄호가 남아있으면 0을 출력하고 그렇지 않으면 숫자들의 합을 구해 출력합니다.

백준 알고리즘 2504번 : https://www.acmicpc.net/problem/2504

문제

상근이의 상상의 친구 외계인은 손가락을 수십억개 가지고 있다. 어느 날 외계인은 기타가 치고 싶었고, 인터넷에서 간단한 멜로디를 검색했다. 이제 이 기타를 치려고 한다.

보통 기타는 1번 줄부터 6번 줄까지 총 6개의 줄이 있고, 각 줄은 P개의 프렛으로 나누어져 있다. 프렛의 번호도 1번부터 P번까지 나누어져 있다.

멜로디는 음의 연속이고, 각 음은 줄에서 해당하는 프렛을 누르고 줄을 튕기면 연주할 수 있다. 예를 들면, 4번 줄의 8번 프렛을 누르고 튕길 수 있다. 만약, 어떤 줄의 프렛을 여러 개 누르고 있다면, 가장 높은 프렛의 음이 발생한다.

예를 들어, 3번 줄의 5번 프렛을 이미 누르고 있다고 하자. 이때, 7번 프렛을 누른 음을 연주하려면, 5번 프렛을 누르는 손을 떼지 않고 다른 손가락으로 7번 프렛을 누르고 줄을 튕기면 된다. 여기서 2번 프렛의 음을 연주하려고 한다면, 5번과 7번을 누르던 손가락을 뗀 다음에 2번 프렛을 누르고 연주해야 한다.

이렇게 손가락으로 프렛을 한 번 누르거나 떼는 것을 손가락을 한 번 움직였다고 한다. 어떤 멜로디가 주어졌을 때, 손가락의 가장 적게 움직이는 회수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 멜로디에 포함되어 있는 음의 수 N과 한 줄에 있는 프렛의 수 P가 주어진다. (N ≤ 500,000, 2 ≤ P ≤ 300,000)

다음 N개 줄에는 멜로디의 한 음을 나타내는 두 정수가 주어진다. 첫 번째 정수는 줄의 번호이고 두 번째 정수는 그 줄에서 눌러야 하는 프렛의 번호이다. 입력으로 주어진 음의 순서대로 기타를 연주해야 한다.

출력

첫째 줄에 멜로디를 연주하는데 필요한 최소 손가락 움직임을 출력한다.

예제 입력과 출력

알고리즘 분류

스택

정답

import sys
input = lambda : sys.stdin.readline().strip()

n, p=map(int,input().split())
a=[list(map(int,input().split())) for i in range(n)]

c=0
ch=[[] for i in range(7)]

for i,j in a:
    if len(ch[i]) == 0:
        ch[i].append(j)
        c +=1
        
    else:
        if j > ch[i][-1]:
            ch[i].append(j)
            c += 1
        elif j == ch[i][-1]: # 이미 있는 경우
            continue
        else: 
            while len(ch[i]) != 0 and j < ch[i][-1]:
                ch[i].pop()
                c += 1
            if len(ch[i]) != 0 and ch[i][-1] == j:
                continue
            ch[i].append(j)
            c += 1

print(c)

1. 기타의 각 줄에 대해 스택을 사용합니다.
2. i 줄의 스택이 비어있으면 값을 추가합니다.
3. i 줄의 스택이 비어있지 않은 경우 스택안의 값과 j 값을 비교합니다.
3-1. j가 스택의 값보다 더 큰 경우 스택에 값을 추가합니다.
3-2. j와 스택의 값이 같은 경우 추가사항 없이 넘어갑니다.
3-3. j가 스택의 값보다 작은 경우 스택의 끝에서부터 j보다 큰 값들을 모두 삭제합니다.
큰 값들을 모두 삭제하고 스택의 값과 j의 값이 같으면 추가사항 없이 넘어가고 그렇지 않으면
스택에 j를 추가합니다.
4. 각 과정마다 손가락 움직인 횟수를 더해 출력합니다.

예제 설명
1 5 : 1 스택의 5 누르기
2 3 : 2 스택의 3 누르기
2 5 : 2 스택의 5 누르기
2 7 : 2 스택의 7 누르기
2 4 : 2 스택의 7 떼기, 2 스택의 5 떼기, 2 스택의 4 누르기
1 5 : 넘어가기(1 스택에 5 있어서)
1 3 : 1 스택의 5 떼기, 1 스택의 3 떼기

따라서 필요한 손가락 움직임의 최소 횟수는 9입니다.

백준 알고리즘 2841번 : www.acmicpc.net/problem/2841