yeony's story

https://www.acmicpc.net/problem/3109 3109번: 빵집 유명한 제빵사 김원웅은 빵집을 운영하고 있다. 원웅이의 빵집은 글로벌 재정 위기를 피해가지 못했고, 결국 심각한 재정 위기에 빠졌다. 원웅이는 지출을 줄이고자 여기저기 지출을 살펴보던 www.acmicpc.net 문제 요약 격자 크기 :R X C map[r][0] = 근처 빵집의 가스관 map[r][c-1]= 원웅이 빵집 건물에는 파이프를 놓을 수 없다. . : 빈칸, x :건물 파이프라인 시작위치 : 첫째 열에서 시작 파이프라인 도착위치 : 마지막 열 연결 가능 위치 :↗, →, ↘ 파이프라인의 경로는 겹칠 수 없고, 서로 접할수도 없다. == 각 칸을 지나는 파이프는 하나여야한다. 가스를 되도록 많이 훔치려고 한다. ..

백트래킹을 사용하여 풀어나간 문제! 이번에는 방문하는 노드 체크 과정을 빼먹지 않고 잘 했다! 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[..

보자마자 백트래킹이 떠올랐던 문제! 백트래킹의 원리는 이해했는데 자꾸 방문처리 체크하는 부분을 빼먹어서 애를 먹는다; 백트래킹 dfs(depth,now): if depth==n: return #함수 종료 for i in range(n): if visited[i]: continue visited[i]=1 dfs(depth+1,now) visited[i]=0 문제를 풀긴 풀었는데 시간이 7140ms..? 허허.. 최대한 필요 없는 과정 제외했다고 생각했는데 ㅠㅠ... s_team에는 스타트팀에 들어간 팀원의 번호 t_team에는 링크팀에 들어간 팀원의 번호를 넣었다. func함수에서 각 팀의 능력치를 계산하고 최소인지 아닌지 판별하여 answer에 값을 넣는다. n = int(input()) s = [lis..

초기 max값은 1 * 1e9 초기 min값은 -1*1e9 이 문제는 백트래킹 개념을 사용하면 풀 수 있다. for문을 돌려서 해야하나 잠시 고민했는데 재귀함수만 이용해도 충분히 가능했던 문제! (아직 재귀함수 사용하는 게 서투른 편..) + , - , * , / 순으로 if문 작성 (주의해야 할 부분) 또, 나눗셈은 정수 나눗셈으로 몫만 취한다. 음수를 양수로 나눌 때는 C++14의 기준을 따른다. 즉, 양수로 바꾼 뒤 몫을 취하고, 그 몫을 음수로 바꾼 것과 같다. 나는 temp가 음수일 때, 양수일때를 나눠서 처리해줘야하는 줄 알았다. 그러나 파이썬 연산자만 잘 활용해도 충분히 간단하게 풀 수 있었다. 파이썬 연산자에서 나눗셈을 담당하는 연산자는 총 3가지 1. / : 나누기 2. // : 나누기 ..

이 문제도 역시나 백트래킹 python3로 돌리면 시간초과가 나서 pypy3로 돌렷다 ㅠㅠ 그래도 시간이 많이 나오긴 하는데 효율적인 코드를 좀 뒤져봐야 할 것 같다! n = int(input()) array = list(map(int, input().split())) operator = list(map(int, input().split())) # +, -, *, // str_operator = [] for idx, i in enumerate(operator): if idx == 0: for j in range(i): str_operator.append('+') continue elif idx == 1: for j in range(i): str_operator.append('-') continue eli..

n = int(input()) array = list(map(int, input().split())) visited = [0 for i in range(n)] answer = 0 new_array = [] def dfs(cnt, new_array): global answer if cnt == n: answer = max(answer, sum(abs(new_array[i]-new_array[i+1]) for i in range(n-1))) return for i in range(n): if visited[i]: #방문한 곳이라면? continue visited[i] = 1 new_array.append(array[i]) dfs(cnt + 1, new_array) visited[i] = 0 new_array..

n = int(input()) array = [list(map(int, input().split())) for _ in range(n)] visited = [[0 for _ in range(n)] for _ in range(n)] answer = float('INF') dx = [1, -1, 0, 0, 0] # 상,하,좌,우,중앙 dy = [0, 0, -1, 1, 0] def check(r, c): global n for i in range(5): nx = r + dx[i] ny = c + dy[i] if visited[nx][ny] or 0 > nx or nx > n - 1 or 0 > ny or ny > n - 1: return False return True def dfs(r, cost, cnt):..