전체 글

[Python] 2636 - 치즈 (골드4)

1. 문제 설명 https://www.acmicpc.net/problem/2636 2636번: 치즈 첫째 줄에는 사각형 모양 판의 세로와 가로의 길이가 양의 정수로 주어진다. 세로와 가로의 길이는 최대 100이다. 판의 각 가로줄의 모양이 윗 줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진 www.acmicpc.net 2. 아이디어 너비 우선 탐색(BFS, Breadth-First Search)를 처음으로 사용해본 문제였다. 해당 알고리즘을 알면 매우 쉽게 해결할 수 있는 문제이지만, BFS를 모르면 이해가 안 갈 수 있다. 알고리즘에 대한 설명은 Algorithm 탭에서 한 번에 다루도록 하고 bfs를 사용하여 어떻게 문제를 해결할 수 있는가에 대한 아이디어만 다루도록 하겠다. 우선 가장 테두리는 언제..

[Python] 1912 - 연속합 (실버2)

1. 문제 설명 https://www.acmicpc.net/problem/1912 1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net 2. 아이디어 수를 차례대로 읽으면서 값을 더하는데 조건을 몇 가지 추가해주면 끝나는 문제다. 만약 현재 누적값이 음수라면 굳이 음수를 유지할 이유가 있을까? 과감히 버리고 새로운 값을 그대로 할당시켜버리면 된다. result는 순열의 첫 번째 값을 저장해두었다가 누적값이 result보다 작으면 그때마다 result를 갱신하면 된다. 그리 어렵지 않게 풀 수 있는 문제. 3. 코드 def s..

[Python] 1058 - 토너먼트 (실버3)

1. 문제 설명 https://www.acmicpc.net/problem/1057 1057번: 토너먼트 김지민은 N명이 참가하는 스타 토너먼트에 진출했다. 토너먼트는 다음과 같이 진행된다. 일단 N명의 참가자는 번호가 1번부터 N번까지 배정받는다. 그러고 난 후에 서로 인접한 번호끼리 스타를 www.acmicpc.net 2. 아이디어 좀 무식하게 풀이한 감이 있다. (1, 2), (3, 4), (5, 6) 이런 식으로 매칭을 해야 되는데 코드를 너무 대충 짰었는지 4번이 5번이랑 대결을 하고 우승을 하질 않나 별 이상한 코드가 만들어져서 그걸 보완하다가 지저분해진 거 같다. 만약 지금 다시 풀어보라고 한다면.. while문 조건에 kim != im을 넣고 kim -= kim // 2, im -= im /..

[Python] 14500 - 테트로미노 (골드5)

1. 문제 설명 https://www.acmicpc.net/problem/14500 14500번: 테트로미노 폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변 www.acmicpc.net 내 첫 골드 문제였다!! 그리고 인생의 쓴 맛을 경험했었다. 난 이게 왜 아직도 고작 골드5밖에 안 되는지 모르겠다. 너무 화나서 함수 이름도 foku라고 지었다... 'ㅗ' 모양 테트로미노를 만들기 위한 전용 함수였으니 완전히 틀린 함수명은 아니다. 2. 아이디어 N, M의 범위가 크지 않기 때문에 전탐색을 써도 무방하다. 모든 row, col을 기준으로 이동가능한 모든 경로를 ..