이것 저것 올리는 곳

https://www.acmicpc.net/problem/1931 1931번: 회의실 배정 (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다. www.acmicpc.net 문제 회의 시작시간과 끝나는 시간을 알려주고, 최대한 많은 회의가 가능한 횟수를 출력하는 문제다. 처음 접근 했던 방식은 시작 시간을 기준으로 정렬하고, 전체 회의 시간 중 하나를 기준으로 잡고 잡은 기준으로 회의를 시작했을 때, 몇 번의 회의를 할 수 있는지 카운트하는 방식으로 풀었었다. n = int(input()) arr = [] for i in range(n) : arr.append(list(map(int, input().split()))) arr = sorted(arr, key=lambda x:x[0])..

알고리즘 문제풀이 2023. 7. 5. 23:44

https://www.acmicpc.net/problem/1012 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 www.acmicpc.net 문제 상하좌우 1이 인접한 뭉치가 몇 개나 있는지 구하는 문제다. BFS/DFS문제는 처음 풀어본다. https://www.youtube.com/watch?v=e7_H8SLZlHY 때문에 여기서 나오는 첫번째 문제에서 힌트를 많이 얻었다. BFS로도 풀어보려고 했는데 BFS는 아직 이해가 되지 않는다. 정답 import sys sys.setrecursionlimit(10000) def dfs(x2, y2) :..

알고리즘 문제풀이 2023. 6. 29. 18:13

https://www.acmicpc.net/problem/1932 1932번: 정수 삼각형 첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다. www.acmicpc.net 문제 정수 삼각형에서 위에서부터 아래로 내려오면서 최댓값을 구할 수 있는 경로를 찾아 최댓값을 구하면 되는 문제다. 문제를 보고 인덱싱을 어떻게 할지 고민했다. 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 이렇게 인덱스를 처리하자니,, 규칙성을 못찾아서 포기하고 새로운 방법을 생각해 냈다. 0 0 1 0 1 2 0 1 2 3 0 1 2 3 4 이렇게 인덱스를 부여하면 쉽게 인덱싱을 할 수 있다. 2차원 리스트로 정리하면 이렇게 정리할 수 있다. arr..

알고리즘 문제풀이 2023. 6. 29. 11:54

https://www.acmicpc.net/problem/1149 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 문제 N개의 집을 색칠할 때 드는 비용이 입력 값으로 준다. 그리고 양옆의 집들과는 색이 달라야 한다. 이때, 집을 색칠할때 발생하는 비용의 최솟값을 구하는 문제이다. 문제를 풀때 조금 헷갈렸다. 집이 3개가 있을 때, 1번 집을 칠하고 2번 집을 칠할 때 1번집을 칠할때 사용했던 색을 제외한 두 가지 색을 각각 칠하는 경우, 그리고 3번 집을 칠할때도 똑같이 2번 집을 칠한..

알고리즘 문제풀이 2023. 6. 28. 17:08

https://www.acmicpc.net/problem/9461 9461번: 파도반 수열 오른쪽 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 변의 www.acmicpc.net 문제 문제에 수열이 나와있어서 쉽게 풀 수 있었다. dp[n] = dp[n-3] + dp[n-2]으로 풀면 되는 문제 정답 dp_arr = [0 for _ in range(101)] dp_arr[0] = 1 dp_arr[1] = 1 dp_arr[2] = 1 for i in range(3, 101, 1) : dp_arr[i] = dp_arr[i-3] + dp_arr[i-2] t = int(input())..

알고리즘 문제풀이 2023. 6. 22. 18:23

https://www.acmicpc.net/problem/1904 1904번: 01타일 지원이에게 2진 수열을 가르쳐 주기 위해, 지원이 아버지는 그에게 타일들을 선물해주셨다. 그리고 이 각각의 타일들은 0 또는 1이 쓰여 있는 낱장의 타일들이다. 어느 날 짓궂은 동주가 지원이 www.acmicpc.net 문제 '1' '00' 이 두 개의 문자열을 이용해 n에 해당하는 문자열을 만들면 되는 문제 같았다. 일단 문제를 읽고 대충 생각나는 대로 재귀로 풀어봤다. def make_bin(s) : if len(s) == n : return 1 elif len(s) > n : return 0 else : return make_bin(s+'00') + make_bin(s+'1') n = int(input()) s ..

알고리즘 문제풀이 2023. 6. 22. 18:12

https://www.acmicpc.net/problem/9184 9184번: 신나는 함수 실행 입력은 세 정수 a, b, c로 이루어져 있으며, 한 줄에 하나씩 주어진다. 입력의 마지막은 -1 -1 -1로 나타내며, 세 정수가 모두 -1인 경우는 입력의 마지막을 제외하면 없다. www.acmicpc.net 문제 문제는 단순하다. 재귀로 구현된 코드를 dp코드로 바꾸라는 거다. dp 입문할 때 풀면 정말 좋은 문제인것 같다. 왜냐하면 이론으로 대충알던 dp를 어느 정도 감을 잡게 해준 문제라고 생각하기 때문이다. 정답 import sys def w(a, b, c) : global dp_arr if a 20 : return w(20, 20, 20) elif a < b and b < c : if dp_arr..

알고리즘 문제풀이 2023. 6. 20. 01:07

https://www.acmicpc.net/problem/5525 5525번: IOIOI N+1개의 I와 N개의 O로 이루어져 있으면, I와 O이 교대로 나오는 문자열을 PN이라고 한다. P1 IOI P2 IOIOI P3 IOIOIOI PN IOIOI...OI (O가 N개) I와 O로만 이루어진 문자열 S와 정수 N이 주어졌을 때, S안에 PN이 몇 www.acmicpc.net 문제 문자열을 입력받고 Pn에 만족하는 게 몇 개나 포함되어 있는지 구하는 문제다. 처음엔 그냥 단순하게 생각했다. 서브태스크있는거 보고 만점은 못 받겠다 하며 풀었다. 50점 코드 n = int(input()) m = int(input()) s = input() Pn = 'I'+'OI'*n count = 0 for i in ra..

알고리즘 문제풀이 2023. 6. 19. 00:01