본문 바로가기

Problem Solving83

[Python]1865. 동철이의 일 분배 https://www.swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5LuHfqDz8DFAXc SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! www.swexpertacademy.com 이 문제는 일반적인 DFS로 풀면 시간초과가 발생한다. 적절한 시점에 Back Tracking 으로 가지치기를 하면(6번줄) 수행시간을 대폭 줄일 수 있다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 def norm(a): return int(a)/100 def dfs(depth, prob): global n, answe.. 2019. 5. 11.
[Python]13460. 구슬 탈출 2 https://www.acmicpc.net/problem/13460 13460번: 구슬 탈출 2 첫 번째 줄에는 보드의 세로, 가로 크기를 의미하는 두 정수 N, M (3 ≤ N, M ≤ 10)이 주어진다. 다음 N개의 줄에 보드의 모양을 나타내는 길이 M의 문자열이 주어진다. 이 문자열은 '.', '#', 'O', 'R', 'B' 로 이루어져 있다. '.'은 빈 칸을 의미하고, '#'은 공이 이동할 수 없는 장애물 또는 벽을 의미하며, 'O'는 구멍의 위치를 의미한다. 'R'은 빨간 구슬의 위치, 'B'는 파란 구슬의 위치이다. 입력되는 모든 보드 www.acmicpc.net 어느 방향으로 기울이는가에 따라 queue에 Red와 Blue의 좌표를 초기화 해주어야 한다.(중요!) 또한 현재 Red 와 B.. 2019. 5. 10.
[Python]14502. 연구소 https://www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크기가 N×M인 직사각형으로 나타낼 수 있으며, 직사각형은 1×1 크기의 정사각형으로 나누어져 있다. 연구소는 빈 칸, 벽으로 이루어져 있으며, 벽은 칸 하나를 가득 차지한다. 일부 칸은 바이러스가 존재하며, 이 바이러스는 상하좌우로 인접한 빈 칸으로 모두 퍼져나갈 수 있다. www.acmicpc.net 문제를 풀기전에 제약조건을 먼저 확인하고 경우의수를 계산해본다. 3 ≤ N, M ≤ 8 이고 벽은 3개를 배치하므로, N*M Combina.. 2019. 5. 9.
[Python]12100. 2048 (Easy) https://www.acmicpc.net/problem/12100 12100번: 2048 (Easy) 첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다. 블록에 쓰여 있는 수는 2보다 크거나 같고, 1024보다 작거나 같은 2의 제곱꼴이다. 블록은 적어도 하나 주어진다. www.acmicpc.net 브루트포스문제라고 생각하며 재귀호출을 통해서 모든 경우의 수를 탐색한다. 매 move마다 check 배열을 생성해서 병합이 되어있는지 안되어있는지 검새를 해주는 것이 포인트 이다. 현재 자신의 위치와 다음 위치 모두가 병합된 적이 없어야만 병합을 시켜준다. 또한, 네가지 방향으로.. 2019. 5. 8.
[Python]1248. 맞춰봐 https://www.acmicpc.net/problem/1248 1248번: 맞춰봐 문제 규현이는 멍청하다. 왜냐하면, 1~10까지 수 밖에 모르기 때문이다. 어느날 규현이 옆을 지나가던 태석이가 규현이를 보고 이렇게 외쳤다. "빵빵!!" 규현이는 "아하!" 하면서 세상에는 빵이란 수도 있구나 했다. 그날 이후로 규현이는 매일 친구들을 볼 때면 "빵빵!!" 거리면서 인사를 했다. 규현이의 친구 중에는 태방이가 있다. 자꾸 규현이가 "빵빵!!" 거릴때 마다 자신을 놀리는 것 처럼 생각했던 태방이는 규현이에게 그건 "빵이 아니고 영이야" 라 www.acmicpc.net 12345678910111213141516171819202122232425262728293031323334353637383940414243.. 2019. 4. 22.
[Python]14889. 스타트와 링크 https://www.acmicpc.net/problem/14889 14889번: 스타트와 링크 예제 2의 경우에 (1, 3, 6), (2, 4, 5)로 팀을 나누면 되고, 예제 3의 경우에는 (1, 2, 4, 5), (3, 6, 7, 8)로 팀을 나누면 된다. www.acmicpc.net 이 문제는 0*n//2 와 1*n//2 로 이루어진 n 길이의 순열을 만들어서 이중포문에 넣으면 되는 간단한 문제이다. 12345678910111213141516171819202122232425262728293031323334353637383940414243def next_perm(a): i = len(a)-1 while i > 0 and a[i-1] >= a[i]: i -= 1 if i = a[j]: j -= 1 a.. 2019. 4. 22.
[Python]17143. 낚시왕 https://www.acmicpc.net/problem/17143 17143번: 낚시왕 낚시왕이 상어 낚시를 하는 곳은 크기가 R×C인 격자판으로 나타낼 수 있다. 격자판의 각 칸은 (r, c)로 나타낼 수 있다. r은 행, c는 열이고, (R, C)는 아래 그림에서 가장 오른쪽 아래에 있는 칸이다. 칸에는 상어가 최대 한 마리 들어있을 수 있다. 상어는 크기와 속도를 가지고 있다. 낚시왕은 가장 처음에 1번 열의 한 칸 왼쪽에 있다. 다음은 1초 동안 일어나는 일이며, 아래 적힌 순서대로 일어난다. 낚시왕은 가장 오른쪽 열의 오른쪽 칸에 www.acmicpc.net 1234567891011121314151617181920212223242526272829303132333435363738394041424.. 2019. 4. 18.
[Python]2529. 부등호 https://www.acmicpc.net/problem/2529 2529번: 부등호 여러분은 제시된 부등호 관계를 만족하는 k+1 자리의 최대, 최소 정수를 첫째 줄과 둘째 줄에 각각 출력해야 한다. 단 아래 예(1)과 같이 첫 자리가 0인 경우도 정수에 포함되어야 한다. 모든 입력에 답은 항상 존재하며 출력 정수는 하나의 문자열이 되도록 해야 한다. www.acmicpc.net 1234567891011121314151617181920212223242526272829303132333435363738def recur(idx): if len(tmp) == k+1: result.append(tmp[:]) return for i in range(10): if idx == -1 and candi[i]: tmp... 2019. 4. 16.
[Python]17127. 벚꽃이 정보섬에 피어난 이유 https://www.acmicpc.net/problem/17127 17127번: 벚꽃이 정보섬에 피어난 이유 다음과 같이 나누는 것이 P의 합을 최대화 한다: [2] [5 3 1 4] [2] [3] www.acmicpc.net 123456789101112131415161718192021222324252627282930def recur(remainder, length): global answer if length == 0: if remainder == 0: v = 0 local_maximum = 0 for i in tmp: local_maximum += mul(a[v:v+i]) v += i answer = max(answer, local_maximum) return for i in range(1,rema.. 2019. 4. 14.
728x90
반응형

티스토리툴바