A DNA sequence can be represented as a string consisting of the letters A, C, G and T, which correspond to the types of successive nucleotides in the sequence. Each nucleotide has an impact factor, which is an integer. Nucleotides of types A, C, G and T have impact factors of 1, 2, 3 and 4, respectively. You are going to answer several queries of the form: What is the minimal impact factor of nucleotides contained in a particular part of the given DNA sequence?

The DNA sequence is given as a non-empty string S = S[0]S[1]...S[N-1] consisting of N characters. There are M queries, which are given in non-empty arrays P and Q, each consisting of M integers. The K-th query (0 ≤ K < M) requires you to find the minimal impact factor of nucleotides contained in the DNA sequence between positions P[K] and Q[K] (inclusive).

For example, consider string S = CAGCCTA and arrays P, Q such that:

P[0] = 2    Q[0] = 4
P[1] = 5    Q[1] = 5
P[2] = 0    Q[2] = 6

The answers to these M = 3 queries are as follows:

The part of the DNA between positions 2 and 4 contains nucleotides G and C (twice), whose impact factors are 3 and 2 respectively, so the answer is 2. The part between positions 5 and 5 contains a single nucleotide T, whose impact factor is 4, so the answer is 4. The part between positions 0 and 6 (the whole string) contains all nucleotides, in particular nucleotide A whose impact factor is 1, so the answer is 1. Write a function:

def solution(S, P, Q)

that, given a non-empty string S consisting of N characters and two non-empty arrays P and Q consisting of M integers, returns an array consisting of M integers specifying the consecutive answers to all queries.

Result array should be returned as an array of integers.

For example, given the string S = CAGCCTA and arrays P, Q such that:

P[0] = 2    Q[0] = 4
P[1] = 5    Q[1] = 5
P[2] = 0    Q[2] = 6

the function should return the values [2, 4, 1], as explained above.

Write an efficient algorithm for the following assumptions:

N is an integer within the range [1..100,000]; M is an integer within the range [1..50,000]; each element of arrays P and Q is an integer within the range [0..N - 1]; P[K] ≤ Q[K], where 0 ≤ K < M; string S consists only of upper-case English letters A, C, G, T.

처음 접근

• 전체 문자열 배열을 숫자로 치환하고 매번 min 값을 구하도록 함
• 시간 복잡도 초과

최종 접근

def solution(S, P, Q):
    # write your code in Python 3.8.10
    listA=[0]
    listC = [0]
    listG = [0]

    idxA = 0
    idxC = 0
    idxG = 0 

    for ch in S:
        if ch == "A":
            idxA +=1
            listA.append(idxA)
            listC.append(idxC)
            listG.append(idxG)
        elif ch == "C":
            idxC +=1
            listA.append(idxA)
            listC.append(idxC)
            listG.append(idxG)
        elif ch == "G":
            idxG +=1
            listA.append(idxA)
            listC.append(idxC)
            listG.append(idxG)
        else:
            listA.append(idxA)
            listC.append(idxC)
            listG.append(idxG)

    #print(listA,listC,listG)

    total = []
    for i in range(len(P)):
        left = P[i]
        right = Q[i]+1
        num = 4
        if listA[right] - listA[left] >0:
            num =1
        elif listC[right] -listC[left]>0:
            num =2
        elif listG[right] - listG[left]>0:
            num =3
        total.append(num)

    return total

• A,C,G 에 대한 리스트를 만든다.
• 문자열에서 해당하는 문자 값이 나오면 list에 값을 추가해서 더한다.
• 최종적으로 검사할때는 해당 범위내에서 변화가 있는지만 감지하면 된다.
• 변화가 없으면 default인 4
• 시간 복잡도는 O(m*n)

increase(X) − counter X is increased by 1, max counter − all counters are set to the maximum value of any counter. A non-empty array A of M integers is given. This array represents consecutive operations:

if A[K] = X, such that 1 ≤ X ≤ N, then operation K is increase(X), if A[K] = N + 1 then operation K is max counter. For example, given integer N = 5 and array A such that:

A[0] = 3
A[1] = 4
A[2] = 4
A[3] = 6
A[4] = 1
A[5] = 4
A[6] = 4

the values of the counters after each consecutive operation will be:

(0, 0, 1, 0, 0)
(0, 0, 1, 1, 0)
(0, 0, 1, 2, 0)
(2, 2, 2, 2, 2)
(3, 2, 2, 2, 2)
(3, 2, 2, 3, 2)
(3, 2, 2, 4, 2)

The goal is to calculate the value of every counter after all operations.

Write a function:

def solution(N, A)

that, given an integer N and a non-empty array A consisting of M integers, returns a sequence of integers representing the values of the counters.

Result array should be returned as an array of integers.

For example, given:

A[0] = 3
A[1] = 4
A[2] = 4
A[3] = 6
A[4] = 1
A[5] = 4
A[6] = 4

the function should return [3, 2, 2, 4, 2], as explained above.

Write an efficient algorithm for the following assumptions:

N and M are integers within the range [1..100,000]; each element of array A is an integer within the range [1..N + 1].

• 첫번째 풀이 문제 내용을 그대로 구현 시간 초과

-두번째 풀이

def solution(N, A):
    # write your code in Python 3.8.10

    num_dic = {}
    max_num = 0
    for num in A:
        num-=1
        if num >= N:
            max_num +=find_max(num_dic)
            num_dic={}
        elif num in num_dic:
            num_dic[num]+=1
        else:
            num_dic[num] = 1

    num_list= [max_num]*N

    for key in num_dic.keys():
        num_list[key] += num_dic[key]    

    return num_list

def find_max(num_dic):
    max_val = 0 
    for key in num_dic.keys():
        max_val = max(max_val,num_dic[key])
    return max_val

• max 값을 찾는 것이 큰 오버헤드가 되는 것을 발견,
• 전체 배열에서 max값을 찾는것이 비효율적이라고 생각해서, count된것만 넣는 dict 생성
• dict에서 max값 찾아주는 함수 만듬

Given the root of a Binary Search Tree and a target number k, return true if there exist two elements in the BST such that their sum is equal to the given target.

Example 1:

Input: root = [5,3,6,2,4,null,7], k = 9 Output: true Example 2: Input: root = [5,3,6,2,4,null,7], k = 28 Output: false

Constraints:

The number of nodes in the tree is in the range [1, 10^4]. -10^4 <= Node.val <= 10^4 root is guaranteed to be a valid binary search tree. -10^5 <= k <= 10^5

코드

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
from collections import deque
class Solution:
    def findTarget(self, root: Optional[TreeNode], k: int) -> bool:

        q = deque()

        q.append([root,k])

        while q:
            node, k = q.popleft()                        
            now = node.val
            if k-now != now:
                now = k-now
                answer = self.find_tree(root,now)               

                if answer == True:
                    return answer
            if node.left !=None:
                q.append([node.left,k])
            if node.right !=None:
                q.append([node.right, k])


        return False


    def find_tree(self,root,val):
        #print(root.val, val)
        tmp = False
        if root.val == val:
            return True
        if root.left == None and root.right == None:
            return False 
        if root.val>val and root.left !=None:
            tmp = self.find_tree(root.left,val)
        elif root.val <val and root.right != None:
            tmp = self.find_tree(root.right,val)
        return tmp

문제 풀이

• root node부터 집어 넣어서 짝이되는 걸 찾는다.
• 자기 자신이 복제되지않도록 k-now != now 일때만
• q에다가 집어 넣어서 끝까지 찾아보도록 한다.

빠른 코드

mapp = set()
mapp.add(k-n.val)

• set을 이용하여 node의 나머지 값을 찾는다.

Example 1:

Input: s = "abcabcbb" Output: 3 Explanation: The answer is "abc", with the length of 3. Example 2:

Input: s = "bbbbb" Output: 1 Explanation: The answer is "b", with the length of 1. Example 3:

Input: s = "pwwkew" Output: 3 Explanation: The answer is "wke", with the length of 3. Notice that the answer must be a substring, "pwke" is a subsequence and not a substring.

Constraints:

0 <= s.length <= 5 * 10^4 s consists of English letters, digits, symbols and spaces.

• 문제 코드

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:

        if len(s)<=1:
            return len(s)

        newChar = ""
        maxCount = 0
        nowCount = 0
        for i in range(len(s)):

            if s[i] in newChar:
                for j in range(len(newChar)):
                    if newChar[j]==s[i]:
                        break
                maxCount = max(maxCount, nowCount)

                newChar = newChar[j+1:]+s[i]
                nowCount=  len(newChar)
            else:
                newChar+=s[i]
                nowCount+=1
                maxCount = max(maxCount, nowCount)
        return maxCount

• 문제 풀이
  • 문자열의 맨 앞에서부터 새로운 문자열에 추가하고, 이미 있는 문자면 새로운 문자열에서 해당 문자의 위치를 찾는다.
  • 문자를 찾으면 그 문자 다음부터 새로운 문자를 만든다.
  • 아니면 문자열 길이 갱신
  • worst는 문자열의 ~aa 이런경우일것 같은데, O(n^3)? 인듯

You may assume that each input would have exactly one solution, and you may not use the same element twice.

You can return the answer in any order.

Example 1:

Input: nums = [2,7,11,15], target = 9 Output: [0,1] Explanation: Because nums[0] + nums[1] == 9, we return [0, 1]. Example 2:

Input: nums = [3,2,4], target = 6 Output: [1,2] Example 3:

Input: nums = [3,3], target = 6 Output: [0,1]

• 문제 풀이

  class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        n = len(nums)
        for i in range(n):
            for j in range(i+1,n):
                if target == nums[i]+nums[j]:
                    return[i,j]

• 문제 분석

  • 간단하게 생각해서 Bruteforce로 구성했음 전체 개수가 10^4개라 brute force해도 된다고 생각
  • O(n^2)

• 개선 코드

  class Solution:    
    def twoSum(self, nums: List[int], target: int) -> List[int]:
  
        numDict={}
  
        for i,n in enumerate(nums):
            if n in numDict.keys():
                return [i,numDict[n]]
            else:
                numDict[target-n] = i

• 개선 방안

  • 두개의 합을 구하는 것이기 때문에 Dictionary의 key, value를 이용하면 구할 수 있다.
  • dictionary에 존재하지않으면 target에서 현재 value를 뺀 값을 key로 하고 index를 value로 넣는다.
  • dictionary에 존재할 경우, 내 index와 dictionary의 index를 return한다.
    • 순서는 상관 X
    • O(n)으로 개선

3184. 양

문제 코드

from collections import deque

row, col = list(map(int, input().split()))

board = [[0 for c in range(col)] for r in range(row)]

wolf_list = []
lamb_list = []
death_wolf = 0
death_lamb = 0
for r in range(row):
    tmp_board = input()
    for c in range(col):
        board[r][c] = tmp_board[c]
        if tmp_board[c] == 'v':
            wolf_list.append([r, c])
        if tmp_board[c] == 'o':
            lamb_list.append([r,c])

visited = [[0 for c in range(col)] for r in range(row)]
for i in range(len(wolf_list)):

    x, y = wolf_list[i]

    if visited[x][y] == 1:
        continue
    que = deque()

    que.append([x, y])

    dx = [-1, 1, 0, 0]
    dy = [0, 0, -1, 1]

    one_area = []
    one_area.append([x, y])
    visited[x][y] = 1
    while len(que) > 0:
        x, y = que.popleft()

        for i in range(4):
            next_x = x + dx[i]
            next_y = y + dy[i]

            if 0 <= next_x < row and 0 <= next_y < col and visited[next_x][next_y] == 0 and board[next_x][
                next_y] != '#':
                que.append([next_x, next_y])
                one_area.append([next_x, next_y])
                visited[next_x][next_y] = 1

    lamb_count = 0
    wolf_count = 0

    for x, y in one_area:

        if board[x][y] == 'o':
            lamb_count += 1
        if board[x][y] == 'v':
            wolf_count += 1

    if lamb_count > wolf_count:
        death_wolf += wolf_count
    else:
        death_lamb += lamb_count

print(len(lamb_list) - death_lamb, len(wolf_list) - death_wolf)

문제 풀이

• 영역을 나누면 되는 문제
• 영역을 먼저 나누고, 해당 영역의 wolf와 lamb 숫자를 센다.
• lamb가 많으면 wolf가 죽고 , 반대면 lamb가 죽음
• 죽은만큼 처음 센 갯수에서 빼준다.

17135. 캐슬 디펜스

문제 코드

from itertools import combinations
from collections import deque
import copy
row,col,D = list(map(int,input().split()))

original_board = [[0 for c in range(col)]for r in range(row)]

comb_list = []

for i in range(col):
    comb_list.append(i)

archor_list = list(combinations(comb_list,3))

#print(archor_list)

for i in range(row):
    num_list = list(map(int,input().split()))
    for j in range(col):
        original_board[i][j] = num_list[j]

#print(board)

max_count = 0

for archors in archor_list:
    board = copy.deepcopy(original_board)
    kill = []
    count = 0

    for tot in range(row):
        for archor in archors:
            start = [row-1,archor]

            que = deque()

            que.append([start[0],start[1],1])
            visited = [[0 for c in range(col)]for r in range(row)]
            while len(que)>0:
                x,y,distance = que.popleft()

                if distance > D:
                    break
                if board[x][y] == 1:
                    kill.append([x,y])
                    break
                visited[x][y] = 1

                dx = [0,-1,0]
                dy = [-1,0,1]

                for i in range(3):
                    next_x = x+dx[i]
                    next_y = y+dy[i]

                    if 0<=next_x<row and 0<=next_y<col and visited[next_x][next_y] == 0:
                        que.append([next_x,next_y,distance+1])

        #print(kill)
        for die in kill:
            x,y = die
            if board[x][y] == 1:
                count+=1
                board[x][y]=0
        kill =[]
        #print(board, count)

        for i in range(row-1,0,-1):
            for j in range(col):
                board[i][j] = board[i-1][j]

        for j in range(col):
            board[0][j] = 0

        #print(board)

    max_count = max(max_count,count)


print(max_count)

문제 풀이

• 첫번째 시도

  • 예제는 다 맞았으나 제출하자마자 틀림
  • 반례 1번에서 답이 6이 나옴
  • Kill list를 초기화하지않아서 발생하는 문제임을 파악
  • 해당 부분 해결하니 합격

반례

2 4 2 1 1 1 1 0 1 1 0 answer :5

11053. 가장 긴 증가하는 부분 수열

문제 코드

N = int(input())

num_list= list(map(int,input().split()))

arr  = [0]*1001

for i in range(len(num_list)):
    arr[num_list[i]] = max(arr[:num_list[i]]) + 1

print(max(arr))

문제 풀이

• num_list의 새로운 값은 기존 arr의 값중에서 가장 큰 값보다 +1만큼 length 증가
• max(arr)의 값이 가장 긴 증가 부분 수열

9205. 맥주 마시면서 걸어가기

문제 코드

from collections import deque

T = int(input())


for test in range(T):
    conv = int(input())

    start_x, start_y = list(map(int,input().split()))

    conv_list = []
    for c in range(conv):
        tmp_conv = list(map(int,input().split()))
        conv_list.append(tmp_conv)

    visited = [0]*(conv+1)

    end_x, end_y = list(map(int,input().split()))

    conv_list.append([end_x,end_y])
    que = deque()

    que.append([start_x,start_y])

    end_checker = False
    while len(que)>0:
        now_x,now_y = que.popleft()

        if now_x == end_x and now_y == end_y:
            end_checker = True
            break
        for i in range(conv+1):
            if visited[i] ==0 and abs(now_x - conv_list[i][0]) + abs(now_y - conv_list[i][1]) <= 1000 :
                que.append([conv_list[i][0],conv_list[i][1]])
                visited[i] = 1

    if end_checker:
        print('happy')
    else:
        print('sad')

문제 풀이

• 처음 위치를 큐에 넣음
• end 위치도 conv_list에 같이 넣음
• 현재 위치에서 아직 방문하지 않았거나, 거리가 1000이하인 편의점들을 큐에 넣음
• end위치에 도착하면 break하고 출력

1931. 회의실 배정

문제 코드

N = int(input())

total_list=[]
for i in range(N):
    num_list = list(map(int,input().split()))

    total_list.append(num_list)

total_list.sort(key=lambda x:(x[1],x[0]))

#print(total_list)
start =0
end = 0
count = 0
for i in range(N):
    now_start , now_end = total_list[i]

    if now_start < end:
        continue

    else:
        end = now_end
        count+=1

print(count)

문제 풀이

• 첫번째 시도

  • 끝나는 시간을 기준으로 정렬하고 전체 회의 리스트를 순회
  • 전타임 끝나는 시간 뒤에 시작하는 회의부터 다시 시작하도록 함
  • 반례 1번을 풀지 못하는 경우 발생

• 두번째 시도

  • 끝나는 시간으로 정렬하고, 시작하는 시간으로 한번더 정렬
  • 두가지 조건으로 동시에 정렬하는 파이썬 기능 사용, 잘 알아둘것

반례

2 4 4 1 4 answer : 2

city, size = list(map(int,input().split()))

city_box_list = [[0 for k in range(city)]for l in range(city)]

box_num = int(input())

for b in range(box_num):
    start, end, weight = list(map(int, input().split()))
    city_box_list[start-1][end-1] = weight

#print(city_box_list)

tmp_weight = size
count = 0

end_box_list = [0]*(city)

for i in range(city):
    count+=end_box_list[i]
    end_box_list[i]=0
    for j in range(i,city):
        if city_box_list[i][j] != 0 :
            can_weight = min(tmp_weight,city_box_list[i][j])

            end_box_list[j] += can_weight

            tmp_size = size
            for k in range(city):
                tmp_size-=end_box_list[k]
                if tmp_size<0:
                    end_box_list[k]+=tmp_size
                    for l in range(k+1,city):
                        end_box_list[l] =0
                    break


print(count)

문제 풀이

• 마을에서 내릴 박스의 양을 들고다니는 배열 선언
• 다음 마을에 갔을때 내릴께 있으면 내리고 count 증가
• 더 실을께 있는데 size를 넘으면 마을이 가까운 것부터 실음
• 이미 size를 초과했는데 마을이 더 가까운게 있으면 버리고 가까운거 실음

from itertools import permutations

N = int(input())

graph = [[0 for col in range(N)]for row in range(N)]

for i in range(N):
    num_list = list(map(int,input().split()))
    for j in range(N):
        graph[i][j] = num_list[j]
        if num_list[j] == 0 :
            graph[i][j] = float('INF')

max_count = float('INF')

move = []
for i in range(N):
    move.append(i)

move_list = list(permutations(move,N))

for move in move_list:
    count = 0
    continue_point = False
    for j in range(len(move)-1):
        count += graph[move[j]][move[j+1]]
        if count > max_count:
            continue_point= True
            break
    if continue_point:
        continue

    count += graph[move[j+1]][move[0]]

    if count < max_count:
        max_count = count

print(max_count)

문제풀이

• 주어진 도시의 개수가 충분히 적어 브루트포스가 가능할것으로 판단
• 도시의 순열을 구해서 길이값을 더하고 가장 길이가 작은것을 넣도록 함
• 처음 제출시 시간초과 문제 발생 -> Count를 계산할때 이미 max보다 큰경우는 프루닝 하도록함
• 예시에서는 도시간 거리가 없는것이 0으로 나오므로 이부분을 inf로 바꿔서 수행

from collections import deque

N= int(input())

graph = [[0 for col in range(N)]for row in range(N)]

for i in range(N):
    graph_row = input()
    for j in range(N):
        graph[i][j] = graph_row[j]

visited = [[0 for col in range(N)]for row in range(N)]

count = 0

color_list =["R","G","B"]
for color in range(3):
    while True:
        find = False
        for i in range(N):
            if find == True:
                break
            for j in range(N):
                if graph[i][j] == color_list[color] and visited[i][j] == 0 :
                    start = [i,j]
                    find = True
                    break

        if find == False:
            break

        que = deque()

        que.append(start)

        visited[start[0]][start[1]] = 1

        while len(que)>0:
            x,y = que.popleft()


            dx = [-1,1,0,0]
            dy = [0,0,-1,1]

            for i in range(4):
                next_x = x+dx[i]
                next_y =y+dy[i]

                if 0<=next_x<N and 0<=next_y<N and visited[next_x][next_y] == 0 and graph[next_x][next_y] == color_list[color]:
                    que.append([next_x,next_y])
                    visited[next_x][next_y] = 1

        count+=1


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

color_list =["R","B"]

two_color_count = 0
visited = [[0 for col in range(N)]for row in range(N)]
for color in range(2):
    while True:
        find = False
        for i in range(N):
            if find == True:
                break
            for j in range(N):
                if graph[i][j] == color_list[color] and visited[i][j] == 0 :
                    start = [i,j]
                    find = True
                    break

        if find == False:
            break

        que = deque()

        que.append(start)

        visited[start[0]][start[1]] = 1

        while len(que)>0:
            x,y = que.popleft()

            dx = [-1,1,0,0]
            dy = [0,0,-1,1]

            for i in range(4):
                next_x = x+dx[i]
                next_y =y+dy[i]

                if 0<=next_x<N and 0<=next_y<N and visited[next_x][next_y] == 0 and graph[next_x][next_y] == color_list[color]:
                    que.append([next_x,next_y])
                    visited[next_x][next_y] = 1

        two_color_count+=1

print(count, two_color_count)

문제 풀이

• R,G,B 3개의 값 순서대로 가장 처음 나오는 곳을 찾는다.
• 가장 처음 나온곳을 기준으로 4방향 이동하며 같은 값을 찾는다.
• visited를 갱신하면서 가다가, 더이상 que가 없으면 count를 하나 증가시키고 다시 처음부터 그래프를 찾아서 다음 R,G,B 값을 찾는다.
• 최종 count의 개수가 구역의 개수
• 적록색약은 R을 G와 일치시켜주고 찾는다.

man = int(input())

num_list = list(map(int,input().split()))

max_count = 0
now_count = 0
start_man = num_list[0]
for i in range(1,man):
    if start_man < num_list[i]:
        if max_count < now_count:
            max_count = now_count
        now_count = 0
        start_man = num_list[i]
    else:
        now_count+=1

if now_count > max_count:
    max_count = now_count
print(max_count)

문제 풀이

• 현재값보다 낮은 값이 많은 것들을 찾아나가는 간단한 문제

from itertools import permutations

N,M = list(map(int,input().split()))

num_list = list(map(int,input().split()))

num_list.sort()

result = list(permutations(num_list,M))

result_set = set(result)
result = list(result_set)
result.sort()
for tmp in result:
   tmp_string = ""
   for i in range(len(tmp)):
       tmp_string+=str(tmp[i])+" "

   print(tmp_string)

문제 풀이

• 순열을 물어보는 문제

2751. 수 정렬하기2

문제 코드

import sys
N = int(input())

num_list = []
for i in range(N):

    num = int(sys.stdin.readline())
    num_list.append(num)

num_list.sort()

for i in range(N):
    sys.stdout.write(str(num_list[i])+'\n')

문제 풀이

• 단순히 int(input()), print() 로 하니 시간 초과
• 할께 많을땐 sys를 쓰자

1525. 퍼즐

문제 코드

from collections import deque
import copy

answer = "123456780"
graph = ""

for i in range(3):
    num_list = list(map(int,input().split()))
    for j in range(3):
        graph+=str(num_list[j])

visited_graph_list =set(graph)

que = deque()

que.append((graph,0))

print_idx = 0
result = -1
while len(que)>0:
    tmp_graph,count = que.popleft()

    if tmp_graph == answer:
        result = count
        break

    blank = tmp_graph.find('0')

    dp = [-1,1,-3,3]

    for i in range(4):
        if (i == 0 and blank in [3,6]) or (i ==1 and blank in [2,5]):
            continue

        next_pos = blank+dp[i]

        if 0<=next_pos<9:
            new_graph=""
            for j in range(9):
                if j == blank:
                    new_graph+=tmp_graph[next_pos]
                elif j == next_pos:
                    new_graph+=tmp_graph[blank]
                else:
                    new_graph+=tmp_graph[j]
            #print(new_graph)

            if new_graph not in visited_graph_list:
                que.append((new_graph,count+1))
                visited_graph_list.add(new_graph)
print(result)

문제 풀이

• 처음에는 3*3 이차원배열로 풀려고 했다.
• visited 비교하는데에 너무나 많은 시간이 걸림
• 문자열로 바꿔서 수행하고, 3 <->4 , 6<->7 swap 안하도록 조건 걸어줌
• que에 리스트 형태로 넣는것보다 set으로 넣는게 훨씬 시간 단축 해줌

1449. 수리공 항승

문제 코드

hole_num, length= list(map(int,input().split()))


hole_list = list(map(int,input().split()))

hole_list.sort()

now_tape = 0
count = 0
while len(hole_list)>0:
    new_hole = hole_list.pop(0)

    if new_hole+0.5 <= now_tape:
        continue

    now_tape = new_hole-0.5+length
    count +=1

print(count)

문제 풀이

• 어차피 모든 구멍은 막아야한다.
• 가장 작은 구멍에서 부터 시작해서 -0.5인 위치에 테이프를 붙인다.
• 다음 구멍+0.5의 위치보다 테이프의 길이가 더 길면, 해당 구멍은 막힌거라고 생각할 수 있다.
• 다음 구멍이 안막히면 그 구멍의 -0.5의 위치에서 다시 테이프를 붙인다.
• 모든 구멍이 막힐때 까지 반복

17163. 색종이 붙이기

문제 코드

def paper(idx,count):
    global min_count,result

    if count >= min_count:
        return
    #print_paper()

    if idx == len(one_list):
        min_count = min(min_count,count)
        return

    i, j = one_list[idx]

    if graph[i][j] == 0:
        paper(idx+1,count)
        return

    for size in range(5,0,-1):
        checker = True
        if i+size < 11 and j+size <11:
            for x in range(i,i+size):
                for y in range(j,j+size):
                    if graph[x][y] == 0:
                        checker = False
            if checker and paper_list[size-1]>0:
                for x in range(i, i + size):
                    for y in range(j, j + size):
                        graph[x][y] = 0
                paper_list[size - 1] -= 1
                #print_paper()
                paper(idx+1,count+1)
                for x in range(i, i + size):
                    for y in range(j, j + size):
                        graph[x][y] = 1
                paper_list[size - 1] += 1


graph = [[0 for row in range(10)]for col in range(10)]
one_list = []
for i in range(10):
    num_list = list(map(int,input().split()))

    for j in range(10):
        graph[i][j] = num_list[j]
        if num_list[j] == 1:
            one_list.append([i,j])


paper_list = [5,5,5,5,5]
count = 0
result = 0
min_count = 26

paper(0,0)


if min_count == 26:
    print(-1)
else:
    print(min_count)

문제 풀이

• 처음 시도

  • 5*5짜리 종이를 붙이고 붙인 부분을 0으로 만들어서 몇개 붙이는지 확인해봄
  • 5개가 넘는 종이를 붙이면 -1 출력

• 시도 2

  • 예시 1번을 넣었을때 답이 4가 나와야 하나, 5*5부터 붙이므로 -1을 리턴하는것을 확인
  • 55부터 붙여보고 안되면 44 3*3 순으로 내려가면서 붙여보도록 함
  • 가장 min을 찾아야 하므로 모든 케이스를 다해보고 가장 적은 종이를 붙이는 걸 출력하도록 함

• 시도 3

  • 예시 2번을 넣었을때 답이 5가 나와야 하나, 지금 기준으로는 5*5를 만족하는 답이 그래프 상에 있으면 바로 붙여버림
  • 전부 다 붙이도록 해봐야함

• 시도 4

  • 백트래킹으로 전환함
  • 입력받을때 1이 위치하는 위치를 기록하도록 함
  • 백트래킹을 돌때 인덱스를 통해서 돌도록 함

추가 예시

예시 1번 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 0 0 0 0 1 1 1 1 1 1 0 0 0 0 1 1 1 1 1 1 0 0 0 0 1 1 1 1 1 1 0 0 0 0 1 1 1 1 1 1 0 0 0 0 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 answer : 4 예시 2번 1 1 1 1 1 1 1 0 0 0 1 1 1 1 1 1 1 0 0 0 1 1 1 1 1 1 1 0 0 0 1 1 1 1 1 1 1 0 0 0 1 1 1 1 1 1 1 0 0 0 1 1 1 1 1 0 0 0 0 0 1 1 1 1 1 0 0 0 0 0 1 1 1 1 1 0 0 0 0 0 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 answer : 5

13305. 주유소

문제 코드

node = int(input())

road_list = list(map(int,input().split()))

price_list = list(map(int,input().split()))

total_price = 0

now_price = price_list[0]
for i in range(len(road_list)):
    total_price+=road_list[i]*now_price

    if now_price > price_list[i+1]:
        now_price = price_list[i+1]

print(total_price)

문제 풀이

• 현재까지 가장 가격이 저렴한 기름값으로 계속 간다.
• 새로운 노드에 갈때마다 가격 비교해서 업데이트