[240504] 코딩테스트 문제풀이

1. 에라토스테네스의 채

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

import math
n,m = map(int, input().split())
A = [0] * (n+1)
count = 0
answer = []
for i in range (2,n+1) :
    A[i] = i

count = 0
answer = []
while count < m :
    for i in range(2,n+1) :
        for j in range(i,n+1,i) :
            if A[j] == 0 :
                continue
            else :
                answer.append((count+1, A[j]))
                count += 1
                A[j] = 0

    if count > m :
        break

print(answer[m-1][1])

 

---

2. 2xn 타일링 2

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

n = int(input())
D = [ 0 for _ in range(n+1)]

# 점화식 초기화
D[1] = 1

if n>=2 :
    D[2] = 3

if n>= 3 :
    for i in range(3,n+1) :
        D[i] = (D[i-2] * 2 + D[i-1])%10007

print(D[-1])

 

---

3. 파도반 수열

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

def turn_number(a):
    D = [0 for _ in range(a+1)]
    D[1] = 1
    if a==2 :
        D[2] = 1

    if a==3 :
        D[2] = 1
        D[3] = 1

    if a >= 4 :
        D[2] = 1
        D[3] = 1
        for i in range(4,a+1) :
            D[i] = D[i-3]+D[i-2]

    return D[-1]

n = int(input())
for i in range(n) :
    a = int(input())
    print(turn_number(a))

 

---

4. 퇴사

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

n = int(input())
A = list()
Day = [0] * (n+1)
Money = [0] * (n+1)
D = [0] * (n+2)

for i in range(1,n+1) :
    a,b = map(int, input().split())
    Day[i] = a
    Money[i] = b

for i in range(n,0,-1) :
    if i+Day[i] > n+1 :
        D[i] = D[i+1]

    else :
        D[i] = max(D[i+1],Money[i]+D[i+Day[i]])


print(D[1])

 

 

---

5.  카드 구매하기 (⭐️복습하기)

• dp[1] = p[1]
• dp[2] = dp[1] + p[1] or dp[0] + p[2]
• dp[3] = dp[2] + p[1] or dp[1] + p[2] or dp[0] + p[3]
• dp[4] = dp[3] + p[1] or dp[2] + p[2] or dp[1] + p[3] or dp[0] + p[4]

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

n = int(input())
B = list(map(int, input().split()))

# 각 가격대별 최대 가격 계산
max_prices = [0] * (n+1)
for i in range(1,n+1) :
    for j in range(i) :
        max_prices[i] = max(max_prices[i],max_prices[j]+B[i-j-1])

print(max_prices[n])

 

---

6. 기타줄

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

n,m = map(int,input().split())
six_pack = list()
one_pack = list()

for i in range(m) :
    a,b = map(int,input().split())
    six_pack.append(a)
    one_pack.append(b)

six_pack_min = min(six_pack)
one_pack_min = min(one_pack)
price = list()

# 6개 pack으로만 사는 경우
price.append(((n//6)+1)*six_pack_min)
# 6,1 pack 조합해서 사는 경우
price.append((n//6)*six_pack_min + (n%6)*one_pack_min)
# 1개 pack으로만 사는 경우
price.append(n*one_pack_min)
print(min(price))

 

 

---

7. 팰린드롬 만들기

import collections
s = list(input())
s.sort()
dict_s = collections.Counter(s)
count = 0
center = ''

for i in dict_s :
    if dict_s[i] % 2 != 0 :
        center += i
        count += 1
        s.remove(i)

if count > 1 : print("I'm Sorry Hansoo")

else :
    sentence = ''
    for i in range(0, len(s),2) :
        sentence += s[i]

    print(sentence + center + sentence[::-1])

 

 

---

8.  삼각형 만들기

• 두 변의 길이 합 > 한 변의 길이 합

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

# 삼각형 만들기
import sys
input = sys.stdin.readline
n = int(input())
A = list()
for i in range(n) :
    A.append(int(input()))

A.sort(reverse=True)
for i in range(n-2) :
    if sum(A[i+1:i+3]) > A[i] :
        print(sum(A[i:i+3]))
        break
else : print(-1)

 

---

9.  오셀로 재배치

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

import sys
input = sys.stdin.readline

def re_number(n,one_list,two_list) :
    wb_count = 0
    bw_count = 0

    for i in range(n) :
        if one_list[i] == 'W' and two_list[i] == 'B' :
            wb_count += 1

        elif one_list[i] == 'B'and two_list[i] == 'W' :
            bw_count += 1

    return (max(wb_count, bw_count))

k = int(input())

for i in range(k) :
    n = int(input())
    one_list = list(input())
    two_list = list(input())
    print(re_number(n,one_list,two_list))

 

---

10.  카드 문자열

• 도대체 왜 계속 틀렸다고 나오는지 모르겠음 ㅠㅠ

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

# 카드 문자열
import sys
input = sys.stdin.readline

def turn_word(n,list_a) :
    set_a = set(list_a)
    set_a = list(set_a)
    set_a.sort()
    first = list_a[0]
    print_sentence = list()

    for i in range(0,n) :
        if set_a.index(first) <= set_a.index(list_a[i]) :
            print_sentence.append(list_a[i])
        else :
            print_sentence.insert(0,list_a[i])

    return print_sentence

# input 값 받기
k = int(input())
for i in range(k) :
    n = int(input())
    list_a = list(input().split(" "))
    sentence = turn_word(n,list_a)
    print(''.join(sentence))

 

---

11. 적록색약 (⭐️복습하기)

https://www.acmicpc.net/problemset?sort=ac_desc&algo=6

# 적록색약
# 구역이 몇 개 있는지 구하기 (상하좌우로)

from collections import deque
import copy
directions = [(1,0),(0,1),(-1,0),(0,-1)]
visited_mark = 'v'

def bfs(grid) :
    queue = deque()
    area_cnt = 0
    N = len(grid)
    for row in range(N) :
        for col in range(N) :
            if grid[row][col] != visited_mark :
                currenct_color = grid[row][col]
                queue.append((row,col))
                while queue :
                    curr_x, curr_y = queue.popleft()
                    for dx,dy in directions :
                        next_x, next_y = curr_x + dx, curr_y + dy
                        if 0<= next_x < N and 0 <= next_y < N and currenct_color == grid[next_x][next_y] :
                            queue.append((next_x,next_y))
                            grid[next_x][next_y] = visited_mark

                area_cnt += 1

    return area_cnt



N = int(input())
a = list()
for i in range(N) :
    a.append(list(input()))

b = copy.deepcopy(a)
print(bfs(a))

for i in range(N) :
    for j in range(N) :
        if b[i][j] == 'G' :
            b[i][j] = 'R'

print(bfs(b))

 

 

---

12. 단지번호붙이기 (🥲 해결못함 )

• 출력 맞게 되는 것 같은데 어디서 잘못되었는지 모르겠다 ㅠㅠ 누구한테 물어볼 사람도 없고 ㅠㅠㅠ

from collections import deque

def bfs(grid) :
    queue = deque()
    N = len(grid)
    directions = [(1, 0), (0, 1), (0, -1), (-1, 0)]
    answer = []
    area_cnt = 0
    for i in range(N) :
        for j in range(N) :
            if grid[i][j] != '0' :
                queue.append((i,j))
                s_area_cnt = 0
                while queue :
                    curr_x, curr_y = queue.popleft()
                    grid[curr_x][curr_y] = '0'
                    for dx,dy in directions :
                        next_x, next_y = curr_x+dx, curr_y+dy
                        if 0<=next_x<N and 0<=next_y<N and grid[next_x][next_y] != '0' :
                            queue.append((next_x,next_y))
                            grid[next_x][next_y] = '0'

                    s_area_cnt +=1

                area_cnt += 1
                answer.append(s_area_cnt)

    answer.insert(0,area_cnt)

    return answer

 

---

13.  집합의 표현

• 유니온파인드 개념 이용해서 푸는 문제

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

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10000)
n,m = map(int, input().split())
parent = [0] * (n+1)

def find(a) :
    if a == parent[a] :
        return a
    else :
        parent[a] = find(parent[a])
        return parent[a]

def union(a,b) :
    a = find(a)
    b = find(b)
    if a!=b :
        parent[b] = a

def checkSame(a,b) :
    a =find(a)
    b = find(b)
    if a == b:
        return True
    return False

for i in range(0,n+1) :
    parent[i] = i

for i in range(m) :
    question,a,b = map(int,input().split())
    if question == 0 :
        union(a,b)
    else :
        if checkSame(a,b) :
            print("YES")
        else :
            print("NO")

 

---

 

14. 여행가자 (⭐️복습하기)

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

N = int(input())
M = int(input())
dosi = [[0 for i in range(N+1)] for j in range(N+1)]

def find(a) :
    if a == parent[a] :
        return a
    else :
        parent[a] = find(parent[a])
        return parent[a]

def union(a,b) :
    a = find(a)
    b = find(b)
    if a!=b :
        parent[b] = a

for i in range(1,N+1) : # 도시 연결 데이터 저장
    dosi[i] = list(map(int,input().split()))
    dosi[i].insert(0,0)

route = list(map(int,input().split()))  #여행해야할 도시 정보 저장
route.insert(0,0)

# 대표노드
parent = [0] * (N+1)
for i in range(1,N+1) :
    parent[i] = i

for i in range(1,N+1) :
    for j in range(1,N+1) :
        if dosi[i][j] == 1 :
            union(i,j)

index = find(route[1])
isConnect = True

for i in range(2,len(route)) :
    if index != find(route[i]) :
        isConnect = False
        break

if isConnect :
    print("YES")
else :
    print("NO")

 

---

15. 문자열 반복

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

def str_turn(a,b) :
    A = list(b)
    answer = ''
    for i in range(len(b)) :
        answer += (b[i]*a)
    return answer

n = int(input())
for i in range(n):
    a,b = input().split(" ")
    a = int(a)
    answer = str_turn(a,b)
    print(answer)

 

 

---

16. 단어공부

https://www.acmicpc.net/submit/1157

a = list(input().upper())
a_set = list(set(a))
count_list = []

for i in a_set :
    count = a.count(i)
    count_list.append(count)


max_number = max(count_list)
if count_list.count(max_number) >= 2 :
    print('?')
else :
    index_number = count_list.index(max_number)
    print(a_set[index_number])

 

---

17.  셀프넘버

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

def self_number_df(n) :
    a = list(str(n))
    result = 0
    for i in range(len(a)) :
        result += int(a[i])

    result += n

    return result

self_number = set()
for i in range(10000) :
    self_number.add(self_number_df(i))

for i in range(1,10001) :
    if i not in self_number :
        print(i)