문제

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

입력

코드

import sys
import math

a, b= map(int, sys.stdin.readline().split())
c=int(math.sqrt(b))+1

x=[True]*(c)
x[1]=False
for i in range(2,c):
    if x[i]:
        if i**2 >c: break
        for j in range(i*i, c, i):
            x[j]=False

count=0
for i in range(1,len(x)):
    if x[i]:
        res=i**2
        while True:
            if res < a:
                res *= i
                continue
            if res>b:
                break
            res*=i
            count+=1

print(count)

문제 해결

에라토스테네스의 체를 활용하는 문제이다. 

일일히 소수인지 파악해버리면 시간복잡도가 엄청 높게 나오기 때문에 주의해서 코드를 작성해야한다,

문제

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

출력

코드

n, m = map(int, input().split())
 
# 입력받은 전체 직사각형을 저장하기 위한 리스트(편리한 인덱싱을 위해 행 삽입)
rectangle_input = [[0 for _ in range(m + 1)]]
 
 
for _ in range(n):
    # 라인별로 읽고 rectangle_input에 저장(편리한 인덱싱을 위해 [0] 삽입)
    line_input = [0] + list(map(int, list(input())))
    rectangle_input.append(line_input)
 
 
# 답은 최댓값을 출력해야 하므로, 0으로 시작
ans = 0
 
# 합을 저장할 리스트
s = [[0 for _ in range(m+1)] for _ in range(n+1)]
 
# 리스트 s는 입력받은 직사각형의 1,1부터 영역 내 모든 수의 합을 저장
for row in range(1, n + 1):
    for col in range(1, m + 1):
        s[row][col] = s[row - 1][col] + s[row][col - 1] - s[row - 1][col - 1] + rectangle_input[row][col]
 
 
def sum_cal(x1, y1, x2, y2):
    return s[x2][y2] - s[x2][y1-1] - s[x1-1][y2] + s[x1-1][y1-1]
 
 
# 첫 번째 경우: 전체 직사각형을 세로로만 분할한 경우
for i in range(1, m-1):
    for j in range(i+1, m):
        r1 = sum_cal(1, 1, n, i)
        r2 = sum_cal(1, i+1, n, j)
        r3 = sum_cal(1, j+1, n, m)
        if ans < r1 * r2 * r3:
            ans = r1 * r2 * r3
 
 
# 두 번째 경우: 전체 직사각형을 가로로만 분할한 경우
for i in range(1, n-1):
    for j in range(i+1, n):
        r1 = sum_cal(1, 1, i, m)
        r2 = sum_cal(i+1, 1, j, m)
        r3 = sum_cal(j+1, 1, n, m)
        if ans < r1 * r2 * r3:
            ans = r1 * r2 * r3
 
# 세 번째 경우: 전체 세로 분할 후 우측 가로 분할한 경우
for i in range(1, m):
    for j in range(1, n):
        r1 = sum_cal(1, 1, n, i)
        r2 = sum_cal(1, i+1, j, m)
        r3 = sum_cal(j+1, i+1, n, m)
        if ans < r1 * r2 * r3:
            ans = r1 * r2 * r3
 
# 네 번째 경우: 전체 세로 분할 후 좌측 가로 분할한 경우
for i in range(1, n):
    for j in range(1, m):
        r1 = sum_cal(1, 1, i, j)
        r2 = sum_cal(i+1, 1, n, j)
        r3 = sum_cal(1, j+1, n, m)
        if ans < r1 * r2 * r3:
            ans = r1 * r2 * r3
 
# 다섯번 째 경우: 전체 가로 분할 후 하단 세로 분할한 경우
for i in range(1, n):
    for j in range(1, m):
        r1 = sum_cal(1, 1, i, m)
        r2 = sum_cal(i+1, 1, n, j)
        r3 = sum_cal(i+1, j+1, n, m)
        if ans < r1 * r2 * r3:
            ans = r1 * r2 * r3
 
# 여섯번 째 경우: 전체 가로 분할 후 상단 세로 분할한 경우
for i in range(1, n):
    for j in range(1, m):
        r1 = sum_cal(1, 1, i, j)
        r2 = sum_cal(1, j+1, i, m)
        r3 = sum_cal(i+1, 1, n, m)
        if ans < r1 * r2 * r3:
            ans = r1 * r2 * r3
 
print(ans)

문제 해결

브루트포스 문제이다, 최대한 많은 조건을 꼼꼼히 나눠서 모든 주어진 문제를 해결해야한다.3개의 작은 직사각형으로 만드는 모든 조건을 6가지로 나눠서 세주었다. 자세한 설명은 코드에 주석을 달아 놨으니 참고하면 될것 같다.

문제

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

입력

import sys
input=sys.stdin.readline
from itertools import combinations

n=int(input())
data=[]
for i in range(n):
    data.append(int(input()))
data.sort(reverse=True)

for i in range(n-2):
    if data[i]<data[i+1]+data[i+2]:
        print(data[i]+data[i+1]+data[i+2])
        break
else: print(-1)

문제

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

코드

import sys
input=sys.stdin.readline

n=int(input())
data=[]
for i in range(n):
    if i==0: ds=int(input())
    else: data.append(int(input()))

data.sort(reverse=True)
cnt=0

if n==1: print(0)
else:
    while True:
        if ds>data[0]:
            print(cnt)
            break
        else:
            ds, data[0], cnt= ds+1, data[0]-1, cnt+1
            data.sort(reverse=True)

문제 해결

그리디 알고리즘을 이용하는 문제이다. 문제의 조건대로 하나씩 작성하면 된다. 

문제

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

코드

import sys
input=sys.stdin.readline
from collections import deque

arr=input().strip()
n=int(input())

deq1=deque(arr[:n+1])
deq2=deque(arr[n+1:])

for i in range(n):
    data=list(input().split())
    if data[0]=='L':
        if len(deq1)!=0:
            deq2.appendleft(deq1.pop())
    if data[0]=='D':
        if len(deq2)!=0:
            deq1.append(deq2.popleft())
    if data[0]=='B':
        if len(deq1)!=0:
            deq1.pop()
    if data[0]=='P':
        deq1.append(data[1])

deq=deq1+deq2
for x in deq:
    print(x, end="")

import sys
#(참신한 풀이) 커서를 기준으로 문자열을 스택두개에 나눠 담는 방법
st1 = list(sys.stdin.readline().rstrip())
st2 = []

for _ in range(int(sys.stdin.readline())):
    command = list(sys.stdin.readline().split())
    if command[0] == 'L':
        if st1:
            st2.append(st1.pop())
            
    elif command[0] == 'D':
        if st2:
            st1.append(st2.pop())

    elif command[0] == 'B':
        if st1:
            st1.pop()
            
    else:
        st1.append(command[1])
        
st1.extend(reversed(st2))
print(''.join(st1))

문제해결

풀이 1은 커서를 기준으로 문자열을 deque 두 개로 나눠서 담는 방법을 사용했고,

풀이 2는 커서를 기준으로 문자열을 stack 두 개로 나눠서 담는 방법을 사용했다.

두개의 풀이의 결은 같은 느낌이니 코드 참조 정도만 하면 될 것같다.

스택과 deque의 활용 능력을 키울 수 있는 문제인 것같다