yeony's story

dp를 이용하여 푸는 문제 dp 할 때는 n+1, m+1의 배열로 만든다. 그래야 인덱스 처리를 따로 해주지 않아도 에러가 나지 않는다 :) array 배열 0 0 0 0 0 0 1 2 3 4 0 0 0 0 5 0 9 8 7 6 0 0 0 0 0 dp 배열 0 0 0 0 0 0 1+0 = 1 2+1 = 3 3+3 = 6 4+6 = 10 0 0+1= 1 0+3 = 3 0+6= 6 5+10=15 0 9+1=10 8+10=18 7+18=25 6+25=31 0 0 0 0 0 n, m = map(int, input().split()) array = [list(map(int, input().split())) for _ in range(n)] dp = [[0 for _ in range(m+1)] for _ in ra..

dfs로 푼 문제! 그냥 끝까지 탐색하고 더이상 탐색할 수 없으면 다시 돌아오면 그만! 바깥쪽에 해당하는 0번째 줄만 dfs문을 돌린다. 그리고 맨 마지막줄에 2가 있으면 안쪽까지 탐색이 되는거니까 YES를 출력해주면 되는 문제 그런데 이렇게 하니까 시간이 오래걸렸다 (1243ms) ㅠㅠ import sys sys.setrecursionlimit(3000000) m, n = map(int, input().split()) # m = 행, n = 열 array = [list(map(int, list(input()))) for _ in range(m)] dx = [-1, 1, 0, 0] dy = [0, 0, -1, 1] def dfs(row, col): array[row][col] = 2 for i in ra..

최대한 왼쪽에 있는 값을 선택하게끔 해줘야 한다. 사실 idx 처리하는 부분에 있어서 고민을 좀 했는데 for문 안에 max, min 함수를 이용하면 손쉽게 처리가 가능하다는 것을 알게 되었다. n, k = map(int, input().split()) array = list(input()) answer = 0 for i in range(n): if array[i] == "P": # 사람 for j in range(max(i - k, 0), min(n, i + k + 1)): if array[j] == "H": answer += 1 array[j] = 0 break print(answer)

큰 정사각형에서 작은 정사각형을 빼주면 넓이를 구할 수 있다는 걸 발견하고 그 값을 구해서 K를 곱해주는 방식으로 구현을 하였다. 작은 정사각형의 넓이를 구하는 과정에서 살짝 헤맸으나 최장길이의 값의 인덱스를 활용하면 금방 구할 수 있다. k = int(input()) array = [list(map(int, input().split())) for _ in range(6)] longW = 0 longH = 0 longWidx = 0 longHidx = 0 shortW = 0 shortH = 0 # 왼쪽 : 2, 오른쪽: 1, 위 : 4, 아래 : 3 # longW => 왼쪽, 오른쪽 탐색 # longH => 위, 아래 탐색 for idx, temp in enumerate(array): if temp[0]..

이 문제를 보자마자 dfs로 풀어야겠다고 생각함. 일단 조합하면 안되는 숫자들은 딕셔너리에 저장했다. 1->2인 경우 서로 선택하면 안되는거니까 딕셔너리에 각각 값을 넣어주었다. * 딕셔너리 value값 여러개일 때 처리해줘야 하는 방법 * 딕셔너리의 value값이 여러개일 경우 dic[i] = []로 초기화하고 값은 append를 이용해서 넣어주면 된다. 아이스크림이 총 5개 있다. 1 2 3 4 5 그 중에 3개의 아이스크림을 선택하는 경우의 수를 구하는 문제이다. 근데 조합해선 안될 아이스크림들이 있다. 1번,2번 아이스크림 3,4번 아이스크림 1,3번 아이스크림 -> 즉 1번 아이스크림은 2번,3번과 같이 선택될 수 없다. 2번,3번 아이스크림도 1번 아이스크림과 선택될 수 없다. 이 코드의 핵심..

처음에는 행은 행 따로 열은 열 따로 체크를 해줘야겠다라는 생각이 떠올랐다. 행은 x가 아예 없는 행의 개수를 세어주고 마찬가지로 열도 x가 아예 없는 열의 개수를 세어준다 이렇게 구한 개수중에 큰 값을 출력해주면 된다. 모든 행과 열에 최소한 한 명 이상의 경비원이 배치되어야 한다. 지금 위에서 구한 건 행과 열마다 각각 배치되어야할 경비원의 수를 구한것이다. 만약 행에 있어야할 경비원의 수가 2이고 열에 있어야할 경비원의 수가 3이라고 하자. 문제에서는 모든 행과 열에 경비원이 있어야한다고 했으니까최소한 3명이 있어야 위 조건을 만족할 수 있다. 따라서 max함수를 이용해서 구해주는 것이다. n, m = map(int, input().split()) array = [input() for _ in ra..

보자마자 조합을 써야하는 문제인가 싶었다. 일단 집 위치와 치킨집 위치를 각 배열에 정리해주었다. 탐색하기 편하도록! combinations 함수를 이용하여m개의 치킨집 경우의 수를 뽑아낸다. 도시의 치킨거리가 가장 작게되는 경우의 수를 구하는 거니까.min함수를 이용해야 한다. answer의 초기값은 int형 max값으로 설정 (1 * 10^9)만약 answer의 값이 sum보다 크다면answer에는 sum값을 집어넣어주면 된다. from itertools import combinations n, m = map(int, input().split()) array = [list(map(int, input().split())) for _ in range(n)] houses = [] chickens = [] ..

문제에 나와있는 순서대로만 구현하면 풀리는 문제! 빈칸 : 0, 벽 : 1, 청소한 칸 : 2로 구분하였다. 처음에는 청소한 구역도 1로 처리했는데 이렇게 하면 2번의 c,d조건을 판별할 수 없었다. 그리고 1번이랑 2번을 각각 독립적으로 움직이게끔 하는 과정이 살짝 버거웠다 ㅎ.. 그리고 % 연산자를 활용해야 하는 부분을 잘 기억해야한다.. 매번 헷갈리지만 ^0^ 왼쪽 방향으로 돌릴 땐 (d+3)%4로 해주면 되는데, d에 3을 더하는 이유에 대해 알아야 앞으로도 사용해먹을 수 있을 것 같아서 상세하게 풀어써보기! 방향은 0, 1, 2, 3 이렇게 있다. 3에서 왼쪽으로 움직이면 2가 되어야하는데 이때는 -1을 해주면 된다. 그러나 문제가 있다. 0에서 왼쪽으로 움직이면 방향은 3이 되어야한다. 그래서..

백트래킹을 사용하여 풀어나간 문제! 이번에는 방문하는 노드 체크 과정을 빼먹지 않고 잘 했다! for문에서 시작점 부분을 함수 매개변수로 넘겨주는 부분을 설정하지 않아서 애먹었던... cnt가 6 => 즉, 6개의 숫자를 모두 뽑아낸 경우에는 그 숫자들을 모두 출력한다. print(*array)를 하게 되면, 배열 형식으로 출력되지 않고 1 2 3 4 5 6 이런식으로 출력된다! # k=array[0] # array[1]~array[7] = 원소 배열 def dfs(array, cnt, temp, i): k = array[0] if cnt == 6: print(*temp) return for i in range(i, k + 1): if visited[i]: # 방문한 노드 continue visited[..

오랜만에 bfs 문제를 접했다..! 역시나 오늘도 헤맸다 !.! 문제 해석하기 1 4 2 2 1 (시작점 idx 2 ) 2 -> 왼쪽 1 o -> 오른쪽 4 o -> x -> 오른쪽 1 o -> 왼쪽 2 o -> 왼쪽 4 o o의 개수 = 5개 from collections import deque n = int(input()) array = list(map(int, input().split())) start = int(input()) - 1 visited = [0] * n result = 0 def bfs(start): # start=idx global result queue = deque() queue.append(start) visited[start] = 1 result+=1 while queue: ..