Leta Learns

문제 https://www.acmicpc.net/problem/1541 1541번: 잃어버린 괄호 첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 www.acmicpc.net 꽤 많이 헤맸다. 처음엔 '(', ')' 에 대해서 투 포인터로 문제를 풀어야 하나? 싶어서 일단 입력받은 식을 해체했다. 수 따로 연산자 따로 리스트를 만들고 나면 어떻게든 되겠지~ 라는 생각으로 일단 식을 해체했는데 하고나니 어떻게 해야 할 지 모르겠어서 문제를 제대로 이해하기 위해 노력했다. 식의 값이 최솟값이 되기 위해서는 뺄셈을 기준으로 식을 나누는 게 가장 중요했다. 뺄셈이 ..

문제 https://www.acmicpc.net/problem/1676 1676번: 팩토리얼 0의 개수 N!에서 뒤에서부터 처음 0이 아닌 숫자가 나올 때까지 0의 개수를 구하는 프로그램을 작성하시오. www.acmicpc.net import sys input = sys.stdin.readline def factorial(n): fac = 1 for i in range(1, n+1): fac *= i return fac n = int(input()) ans = factorial(n) strans = str(ans) cnt = 0 for i in range(len(strans)-1, -1, -1): if strans[i] == '0': cnt += 1 else: break print(cnt) #2022-0..

문제 https://www.acmicpc.net/problem/1654 1654번: 랜선 자르기 첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그 www.acmicpc.net 이분탐색 안 하고 그냥 풀어도 되지 않을까.. 하는 희망을 가지고 풀었는데 시간초과 났다. ㅎㅎ 코드도 수정해보고 pypy3로도 해봤는데 안 돼서 결국 이분탐색으로 풀었다. #이분탐색코드 import sys input = sys.stdin.readline k, n = map(int, input().split()) lan = [int(input()) for _ in..

문제 https://www.acmicpc.net/problem/1436 1436번: 영화감독 숌 666은 종말을 나타내는 숫자라고 한다. 따라서, 많은 블록버스터 영화에서는 666이 들어간 제목을 많이 사용한다. 영화감독 숌은 세상의 종말 이라는 시리즈 영화의 감독이다. 조지 루카스는 스타 www.acmicpc.net 어렵게 생각했는데 생각해보니 그냥 1씩 추가하면서 666이 포함된 수를 찾으면 되는 문제였다. 수를 문자열로만 바꿔주면 된다. import sys input = sys.stdin.readline n = int(input()) ans = '666' cnt = 1 while cnt != n: intans = int(ans) intans += 1 ans = str(intans) if '666' ..

문제 https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net DP 오랜만에 푸는 거라 정신 못 차렸다. 어떻게 풀어야 할 지 감이 안 잡혀서 알고리즘 분류 확인하고 디피 문제라는 걸 확인한 후에 풀었다. 디피 연습을 좀 해야할 것 같다. 간단한 코드 설명은 주석으로 적어놓았다. import sys input = sys.stdin.readline n= int(input()) dp = [0 for _ in range(n+1)] for i in range(2, n+1): dp[i] = dp[i-1] + 1 #일단 1은 무조건 빼놓고 (연산 3) if i % 3 == 0:..

문제 https://www.acmicpc.net/problem/1389 1389번: 케빈 베이컨의 6단계 법칙 첫째 줄에 유저의 수 N (2 ≤ N ≤ 100)과 친구 관계의 수 M (1 ≤ M ≤ 5,000)이 주어진다. 둘째 줄부터 M개의 줄에는 친구 관계가 주어진다. 친구 관계는 A와 B로 이루어져 있으며, A와 B가 친구라는 뜻 www.acmicpc.net 자기 자신과의 단계는 0이므로 이를 표현하기 위해 visited의 초기값을 -1로 지정하였다. bfs함수를 호출하면 해당 사람(?)의 visited 값을 0으로 바꾸어준다. (자기자신) 한 번 방문할 때마다 이전에 방문한 친구의 단계에서 1을 더해준다. 케빈 베이컨 수는 모든 사람과 케빈 베이컨 게임을 했을 때 나오는 단계의 합이므로 bfs 함..

문제 https://www.acmicpc.net/problem/1018 1018번: 체스판 다시 칠하기 첫째 줄에 N과 M이 주어진다. N과 M은 8보다 크거나 같고, 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 보드의 각 행의 상태가 주어진다. B는 검은색이며, W는 흰색이다. www.acmicpc.net 인덱스 에러 안 나도록 지정해주는 거랑 (for i in range(n-7)) 짝홀수 구분해서 잘못 칠한 색 찾아내는 방식을 떠올리는데 오래 걸렸다. 아무리 봐도 모르겠어서 다른 사람이 쓴 문제 해석 보면서 풀었다. ... 어렵다. import sys input = sys.stdin.readline n, m = map(int, input().split()) chess = [input(..

문제 https://www.acmicpc.net/problem/1181 1181번: 단어 정렬 첫째 줄에 단어의 개수 N이 주어진다. (1 ≤ N ≤ 20,000) 둘째 줄부터 N개의 줄에 걸쳐 알파벳 소문자로 이루어진 단어가 한 줄에 하나씩 주어진다. 주어지는 문자열의 길이는 50을 넘지 않는다. www.acmicpc.net 문자열 길이 순으로 정렬하는 법 list_name.sort(key=lambda x:len(x)) import sys input = sys.stdin.readline n = int(input()) word = [] for i in range(n): a = input().strip() if a not in word: word.append(a) word.sort() word.sort(k..

문제 https://www.acmicpc.net/problem/15666 15666번: N과 M (12) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net n과 m 처음부터 풀었으면 쉽게 풀 수 있는 문제였다. (10), (11) 코드 적당히 합쳐서 만들면 된다. (11) 코드에 고른 수열이 비내림차순이어야 한다는 조건만 추가해주면 되므로, 시작점을 나타내는 변수 s를 사용하여 현재 값 i 가 시작값인 s 보다 크거나 같은 경우를 골라주면 된다. import sys input = sys.stdin.readline def dfs(s): #s:..

문제 https://www.acmicpc.net/problem/15665 15665번: N과 M (11) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 아 처음에 바로 시도했던 방식이 맞았는데 터미널에서 출력할 때 입출력 구분이 안 돼서 입력 받는 수열까지 출력된 거라고 생각했다. 그래서 다른 방법으로 풀다가 아까 입출력을 헷갈렸다는 것을 깨달았다. 괜히 다른 방법으로 풀었다가 시간초과나고ㅋㅋㅜㅜ 암튼 내가 헛짓해서 그렇지 문제 자체는 n과 m 차례대로 풀었다면 비교적 쉽게 고안할 수 있는 문제였다. 같은 수를 여러 번 골라도 되기 때문..