공부해볼라는 스토리

1. 문제 https://www.acmicpc.net/problem/10844 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 2. 풀이 후하후하 이거 어떻게 DP로 풀어야하나 했는데 ㅠㅠ 전혀 검색을 안해서 순전히 내생각으로 해보자면 1) 내가 지나가야하는 숫자들 2) 지나간 숫자들을 같은 인덱스로 또 다음 후보군으로 만났을때 그 수를 저장 이 두가지를 저장하는 느낌으로? 1. 위 말한 저장할 변수 두 가지를 선언한다. (대신 count변수는 첫째자리 바뀔때마다 매번 초기화) 2. 이제 첫째 자리(index=0)부터 시작한다. (1~9만 가능) ==> queue 선언해서 (i, 0) 로 시작 3. next 가 빌때까지 계속..

1. 문제 https://www.acmicpc.net/problem/17298 17298번: 오큰수 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다. www.acmicpc.net 2. 풀이 사실 이문제는 열심히 풀었는데 계속 시간초과가 났다ㅠ 그래서 도움을 좀 받은,,, 그래도 덕분에 스택을 잘 사용하는 법을 알게됨. 처음엔 그냥 원래 스택 -> 이미 사용한 스택 이렇게 해서 다 검사하게 했는데 생각해보니 뒤에 보낼때 다~~ 검사하는게 아니라 한번이라도 어떤 수보다 작았으면 pop 하면 됐는데ㅠ 그걸몰랐다. 1) NGE, stack 변수를 설정한다. 2) i=n-1부터 돌..

1. 문제 https://www.acmicpc.net/problem/2529 2529번: 부등호 여러분은 제시된 부등호 관계를 만족하는 k+1 자리의 최대, 최소 정수를 첫째 줄과 둘째 줄에 각각 출력해야 한다. 단 아래 예(1)과 같이 첫 자리가 0인 경우도 정수에 포함되어야 한다. 모든 입력 www.acmicpc.net 2. 풀이 1) 숫자를 사용했는지 아닌지 파악하는 visited 변수 설정, max/min 변수 설정 2) bt 함수: 리스트에 숫자 하나는 넣고 시작 ==> 부등호 하나, visited에 방문안했던 (False)인 숫자 가져와서 부등호 만족하는지 확인하고 다음으로 넘김 ==> 만약 다음에 안되는 경우의 수면 더이상 진행안됨 3) idx == n 까지 다오면 그 숫자가 max/min인..

1. 문제 https://www.acmicpc.net/problem/2156 2156번: 포도주 시식 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규 www.acmicpc.net 2.풀이 자세한 풀이는 위 사진으로 설명하겠습니다 !! ## code ## import sys from collections import * n = int(sys.stdin.readline()) grape = [] for _ in range(n): grape.append(int(sys.stdin.readline())) # 0: 이번거 안먹음 , 1: 연속적으로 안먹엇고 이번거 먹음, 2:..

1. 문제 https://www.acmicpc.net/problem/10819 10819번: 차이를 최대로 첫째 줄에 N (3 ≤ N ≤ 8)이 주어진다. 둘째 줄에는 배열 A에 들어있는 정수가 주어진다. 배열에 들어있는 정수는 -100보다 크거나 같고, 100보다 작거나 같다. www.acmicpc.net 2. 풀이 백트래킹도 좀 감이 오는거같다!! 후 코테 이제 드루와 (사실 들어오지 마세요ㅠ 문제는 연속된 숫자끼리의 차이 절댓값을 max로 만드는거고, 우선 백트래킹으로 푸는거에 중점을 뒀다. 1) total_max라는 전역변수 만들어주고, 어디서 처음 계산을 시작할지 한번씩 돌려준다. 2) 백트래킹 함수 내부: 다돌았을때 멈춘다 (return). total이 크면 바꿔준다. visited는 inde..

1. 문제 https://www.acmicpc.net/problem/2579 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net 2. 풀이 정말 정말 오랜 숙원을 풀었다 ㅋㅋㅋㅋㅋ 하 보니까 2년전에도 못풀었던데 DP는 진짜 나한테 어려웠는데 눈앞에 닥친 코테때문에 겁나 열심히 하는중 메모리 초과 -> 맞았습니다!!! 의 여정입니다. 1) 먼저, 저는 솔직히 다른 방법이 크게 생각이 안나서 고민을 많이한게 [1] 배낭문제처럼 테이블로 풀기 [2] 한 리스트에 계속 max 값 업데이트하는 방식 이정도로 고민했는데,, 결론적으로..

실4 1. 문제 https://www.acmicpc.net/problem/2839 2839번: 설탕 배달 상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕공장에서 만드는 설탕은 봉지에 담겨져 있다. 봉지는 3킬로그 www.acmicpc.net 2. 풀이 실버 수준의 그리디/DP 문제이다. 예전에 그리디하게는 풀었었는데, DP로도 풀고 싶어서 다시 풀었다!! 1) Greedy 방법 1-1) 우선 그리디하게 풀어야하니까, 현재상황에서 가장 최선이도록 욕심을 부려야한다 == 5키로를 최대한 들자 ! 1-2) 따라서 간단하다. 현재 주어진 숫자에 5로 나눠서 나눠지면 바로, 아니면 3씩 줄여가면서 5의 배수를 찾아가는지 해보면된다. 마지..

브1 1. 문제 https://www.acmicpc.net/problem/1292 1292번: 쉽게 푸는 문제 첫째 줄에 구간의 시작과 끝을 나타내는 정수 A, B(1 ≤ A ≤ B ≤ 1,000)가 주어진다. 즉, 수열에서 A번째 숫자부터 B번째 숫자까지 합을 구하면 된다. www.acmicpc.net 2. 풀이 코테 준비하면서 구현 문제가 중요하다고 하길래 추천 문제를 풀고있다. 구현 문제들이 브론즈 문제들 추천이 많아서 일단 오랜만에 푸는데, 속도를 더 올려서 빠르게 마무리 할 수 있도록 해야겟다ㅜ___ㅜ 구간합을 구하는 문제인데, ## code ## import sys ''' - 시작 점, 끝점 구해서 ~ 시작 숫자 같은 경우, 뒤에만 고려 ~ 달라서 앞, 중간, 뒤로 나눠서 더하기 ''' sta..

문제 가로, 세로의 크기가 각각 100인 정사각형 모양의 흰색 도화지가 있다. 이 도화지 위에 가로, 세로의 크기가 각각 10인 정사각형 모양의 검은색 색종이를 색종이의 변과 도화지의 변이 평행하도록 붙인다. 이러한 방식으로 색종이를 한 장 또는 여러 장 붙인 후 색종이가 붙은 검은 영역의 넓이를 구하는 프로그램을 작성하시오. 예를 들어 흰색 도화지 위에 세 장의 검은색 색종이를 그림과 같은 모양으로 붙였다면 검은색 영역의 넓이는 260이 된다. 입력 첫째 줄에 색종이의 수가 주어진다. 이어 둘째 줄부터 한 줄에 하나씩 색종이를 붙인 위치가 주어진다. 색종이를 붙인 위치는 두 개의 자연수로 주어지는데 첫 번째 자연수는 색종이의 왼쪽 변과 도화지의 왼쪽 변 사이의 거리이고, 두 번째 자연수는 색종이의 아래..

문제 의 끝자리 0의 개수를 출력하는 프로그램을 작성하시오. 입력 첫째 줄에 정수 n, m (0≤m≤n≤2,000,000,000, n≠0)이 들어온다. 출력 첫째 줄에 계산된 수의 끝자리 0의 개수를 출력한다. 예제 입력 1 25 12 예제 출력 1 2 [풀이] 처음에는 예전에 조합 푼 것처럼 풀었는데 import sys n, m = map(int, sys.stdin.readline().split()) top, bot, zero = 1, 1, 0 if n - m < m: m = n - m bot = m print(top, bot, zero) for i in range(0, m): top *= (n-i) top /= bot bot -= 1 while 1: rest = int(top%10) if rest =..