https://www.acmicpc.net/problem/1182 1182번: 부분수열의 합 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다. www.acmicpc.net 백트래킹으로 풀어보려고 했는데, 일단 내장 combinations 써서 풀었다 .. 1 ~ N개까지 모든 부분 수열을 구해보고 그 합이 S이면 answer 하나씩 증가해주기 import sys from itertools import combinations N,S = map(int, sys.stdin.readline().split()) nums = list(map..

https://www.acmicpc.net/problem/14503 14503번: 로봇 청소기 로봇 청소기가 주어졌을 때, 청소하는 영역의 개수를 구하는 프로그램을 작성하시오. 로봇 청소기가 있는 장소는 N×M 크기의 직사각형으로 나타낼 수 있으며, 1×1크기의 정사각형 칸으로 나누어 www.acmicpc.net 왼쪽으로 회전 또는 후진하기 위해 현재 방향을 key, 회전 또는 후진을 위한 이동 방향을 value로 갖는 딕셔너리를 정의한다. move_dict는 각 방향을 key로, 그 방향으로 이동하기 위한 (dx, dy)를 value로 갖는다. 이후 문제의 조건에 맞게 다음을 반복한다. 왼쪽 방향이 벽도 아니고 아직 청소하지 않은 곳이면 왼쪽으로 회전하고, 그 칸으로 이동해 그 칸을 청소한다(2a). ..

https://www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net 요즘 비슷한 문제를 엄청 많이 풀었다. 다 거기서 거기네.. bfs... 비슷한 bfs 문제들 경쟁적 전염 연구소 감시 피하기 인구 이동 make_ripe 함수로 하루동안 토마토의 변화를 계산한다. 우선 익은 토마토가 있는 좌표들인 tomato를 큐로 만들고, 이들을 하나씩 pop하면서 그 토마토의 인접한 부분 중에 0인 곳이 있으면 1로 바꿔준다. 그리고 이제 익게 되었으니 다음..

https://www.acmicpc.net/problem/2839 2839번: 설탕 배달 상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕공장에서 만드는 설탕은 봉지에 담겨져 있다. 봉지는 3킬로그 www.acmicpc.net 최대한 적은 봉지를 가져가려고 하므로 5kg 봉지를 최대한 활용해야 한다. 우선 q5에 5kg 봉지의 최대 개수를 저장한다. q5를 0까지 하나씩 줄여가면서 5kg 봉지를 해당 개수만큼 들고 갔을 때, 남은 무게가 3의 배수인지 확인한다. 3의 배수라면 5kg 봉지 개수 + 남은 무게를 3으로 나눈 몫이 정답이 된다. 최대한 5kg 봉지를 많이 가져가야 하므로 조건이 충족되면 바로 break로 for loo..

https://www.acmicpc.net/problem/2447 2447번: 별 찍기 - 10 재귀적인 패턴으로 별을 찍어 보자. N이 3의 거듭제곱(3, 9, 27, ...)이라고 할 때, 크기 N의 패턴은 N×N 정사각형 모양이다. 크기 3의 패턴은 가운데에 공백이 있고, 가운데를 제외한 모든 칸에 별이 www.acmicpc.net 로그 함수 때문에 애 먹었다 왜 그러는거야? 왜 log_3(81)은 4.0이고 log_3(243)은 4.99 라서 날 힘들게 만든거야! int가 아니라 round를 써야 했다 재귀함수를 사용했다. [이전 모양 사각형] [이전 모양 사각형] [이전 모양 사각형] [이전 모양 사각형] [ N/3 빈 정사각형] [이전 모양 사각형] [이전 모양 사각형] [이전 모양 사각형] ..

https://www.acmicpc.net/problem/3665 3665번: 최종 순위 올해 ACM-ICPC 대전 인터넷 예선에는 총 n개의 팀이 참가했다. 팀은 1번부터 n번까지 번호가 매겨져 있다. 놀랍게도 올해 참가하는 팀은 작년에 참가했던 팀과 동일하다. 올해는 인터넷 예선 본부에 www.acmicpc.net '?'를 출력하는 경우는 이해가 안 돼서 구현을 못 했는데 통과되어 버렸다... 그래프를 사용하지 않고 dictionary를 사용했다. key는 팀 번호, value는 그 팀보다 순위가 낮은 팀 번호들의 목록 작년 순위에 따라 이 dictionary를 초기화하고, 순위가 바뀐 정보가 들어오면 이에 따라 정보를 업데이트한다. 총 팀의 개수를 M이라고 할 때, 업데이트 후에 각 value의 길..