Algorithm

Python 15686번 치킨 배달

https://www.acmicpc.net/problem/15686 문제에서는 최대 m개의 치킨집이 있을 경우 치킨 거리의 최소합을 구하라고 했다. 먼저 치킨집이랑 사람집을 따로 리스트를 만들어서 보관했고 그 이후 dfs 방식을 이용해서 문제에 접근했다. cnt 즉 고른 치킨집의 개수가 최대 치킨집의 개수와 일치하면 계산을 시작했고 계산한 결과값을 result라는 리스트에 넣어줬다. (처음에 result에 5001이라는 값을 넣어준 이유는 아래 resMin 처음 실행될때 빈 리스트일 경우 에러가 날 수도 있기 때문에 100*100을 확실하게 넣어주는게 맞긴 한데 최대가 5001을 초과할 일이 없어서 잘됐네요 ㅎ,,) 처음에 m개의 치킨집 개수를 loc라는 list에 append나 pop을 이용하려 했는데..

Codeforces Round #817 (Div. 4) 문제 정리 +4

4문제 정도 풀었고 풀었을 때 계속 추가할 예정입니다!! 1. Spell check 이 문제의 경우 처음 읽었을 때 이해가 안갔는데(영어라 이해를 잘못해서 그런가..) 몇번 읽다보니 뭔소린지 이해가 갔다 ㅎㅎ,, 문제 요구사항은 자신의 이름을 여러가지 순열을 허용해서(예시처럼 Trumi, ruTmi 등..) 입력으로 받은 값이 자신의 이름 값으로 유효한지 체크하는 문제이다. 처음엔 이름 구성도 5글자니까 길이는 5로 정해놓고 저 list안에만 포함되면 되겠구나 생각했는데 정답처리가 안되는 케이스가 있었다. 그래서 곰곰히 생각해보니 5글자가 아니여도 즉, 공백 같은게 들어가도 이름인걸 허용하는 케이스도 있다고 생각했고 길이가 5보다 작은 것들만 처리하니까 정답처리가 됐다. import sys input =..

Python 1541번 잃어버린 괄호

https://www.acmicpc.net/problem/1541 1541번: 잃어버린 괄호 첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 www.acmicpc.net 수열 문제라서 되게 코드가 간결할줄 알았는데 짜다보니 코드가 점점 길어지는 것 같다ㅏ,,, 먼저 입력으로 주어진 문자열에서 operator와 num을 다른 리스트로 분리하였고 res라는 리스트를 따로 만들어서 - 이후의 숫자를 계산한 값을 넣도록 만들었다. 예를 들어 55-50+40+30+20-30-25 가 입력으로 주어졌을때 리스트가 [55, '-', 140, '-', 30, '-', 25..

Python 16234번 인구 이동

https://www.acmicpc.net/problem/16234 16234번: 인구 이동 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모 www.acmicpc.net 문제는 방식은 간단했다. 처음부터 끝까지 모든 인덱스를 방문해서(이미 방문한 곳은 패스) bfs방식으로 연결된 구간은(인구 이동이 일어나는 구간) result에 set으로 저장을 해서 res에 저장했다. 그리고 res에 저장된 연결된 구간들의 인구의 값을 모두 더하고 나눈 다음 그 구간에 값들을 다시 재분배해줬다. 이와 같은 방식으로 res에 아무것도 저장이 되지 않을때까지(이어진 ..

Python 16929번 Two Dots

https://www.acmicpc.net/problem/16929 16929번: Two Dots 첫째 줄에 게임판의 크기 N, M이 주어진다. 둘째 줄부터 N개의 줄에 게임판의 상태가 주어진다. 게임판은 모두 점으로 가득차 있고, 게임판의 상태는 점의 색을 의미한다. 점의 색은 알파벳 대문 www.acmicpc.net 문제를 처음 풀때 graph로 딕셔너리를 만들어서 풀려고 했는데 예시의 경우에선 답이 잘나오는데 중간에 예외적인 경우에서 오답처리가 돼서 좀 오랫동안 고민하다가 그냥 dfs의 재귀만 이용해서 풀었더니 정답이 되었다....ㅠ 풀이 방법은 먼저 방문했는지 확인하기 위해 visited라는 2차원 배열을 만들고 현재 칸을 방문했다는 것을 저장하기 위해 visited값을 바꿔주고 그 다음 이제 현..

Python 16928번 뱀과 사다리 게임

https://www.acmicpc.net/problem/16928 16928번: 뱀과 사다리 게임 첫째 줄에 게임판에 있는 사다리의 수 N(1 ≤ N ≤ 15)과 뱀의 수 M(1 ≤ M ≤ 15)이 주어진다. 둘째 줄부터 N개의 줄에는 사다리의 정보를 의미하는 x, y (x < y)가 주어진다. x번 칸에 도착하면, y번 칸으 www.acmicpc.net 문제를 어떻게 풀까 고민하다가 dp랑 bfs를 섞어서 써봤다! 먼저 visited로 dp를 관리했고 bfs로 주사위를 던져서 간 칸의 값을 q에 append해줬다. 하지만 그 칸에 뱀이나 사다리를 타는 칸이 있다면 사다리를 타고 올라간 칸이나 뱀을 타고 내려간 칸을 dp방식을 이용해 주사위를 던진 횟수가 최소가 되는 경우를 해당 칸의 visited에 ..

Python 11048번 이동하기

https://www.acmicpc.net/problem/11048 11048번: 이동하기 준규는 N×M 크기의 미로에 갇혀있다. 미로는 1×1크기의 방으로 나누어져 있고, 각 방에는 사탕이 놓여져 있다. 미로의 가장 왼쪽 윗 방은 (1, 1)이고, 가장 오른쪽 아랫 방은 (N, M)이다. 준규는 www.acmicpc.net 이 문제는 dp를 이용하면 쉽게 문제를 풀 수 있다. 문제에 나와있는데 r+1,c 이런것들을 dx와 dy를 이용해서 표현하였고 dp를 이용해서 전에 있던 값에 이동한 칸의 값을 더한 게 원래 있던 dp값보다 크면 바꾸고 아니면 그대로 유지하도록 했다. import sys cnt=[] input=sys.stdin.readline n,m = map(int,input().split()) ..

Python 14225번 부분수열의 합

https://www.acmicpc.net/problem/14225 14225번: 부분수열의 합 수열 S가 주어졌을 때, 수열 S의 부분 수열의 합으로 나올 수 없는 가장 작은 자연수를 구하는 프로그램을 작성하시오. 예를 들어, S = [5, 1, 2]인 경우에 1, 2, 3(=1+2), 5, 6(=1+5), 7(=2+5), 8(=1+2+5)을 만들 www.acmicpc.net 처음엔 이 문제를 아래처럼 재귀 방식을 이용해서 문제를 풀려고 했지만 시간 초과 에러가 떠서 다른 방법을 구글링 해봤더니 비트마스크를 이용하는 방식을 찾았다. import sys cnt=[] input=sys.stdin.readline num = [0]*2000000 n = int(input()) ary = list(map(int..

Python 2529번 부등호

https://www.acmicpc.net/problem/2529 2529번: 부등호 두 종류의 부등호 기호 ‘’가 k개 나열된 순서열 A가 있다. 우리는 이 부등호 기호 앞뒤에 서로 다른 한 자릿수 숫자를 넣어서 모든 부등호 관계를 만족시키려고 한다. 예를 들어, 제시 www.acmicpc.net 문제에서 주어진 조건은 숫자는 0~9까지의 정수가 들어가고 선택된 숫자가 중복이 되어서는 안되며 부등식을 만족해야하는게 조건이다. 0~9까지의 조건을 만족하기 위해서 num은 0~9까지 반복되고 선택된 숫자가 중복되었는지 확인하기 위해서 visited라는 list를 이용하여 숫자가 사용되었는지 확인하였다. 그리고 매회마다 이전 숫자와 현재 숫자를 비교해서 부등식이 일치하면 res라는 변수에 숫자를 문자열로 추..

Python 1182번 부분수열의 합

https://www.acmicpc.net/problem/1182 1182번: 부분수열의 합 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다. www.acmicpc.net 이 문제는 재귀 방식을 이용한 브루트 포스 방식으로 문제를 풀었다. 문제에서 조건이 크기가 양수인 부분 수열이기 때문에 수열의 크기가 0보다 크고 합이 s와 같을 경우에 cnt라는 리스트에 저장하도록 하여 cnt리스트의 개수가 출력되도록 하였다. import sys cnt=[] input=sys.stdin.readline def recur(i,res,sum,s,..