빙수의 팝콘

11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 문제 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다. 입력 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는..

문제 정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다. X가 3으로 나누어 떨어지면, 3으로 나눈다. X가 2로 나누어 떨어지면, 2로 나눈다. 1을 뺀다. 정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오. 입력 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. 출력 첫째 줄에 연산을 하는 횟수의 최솟값을 출력한다. 가장 쉬우면서도 대표적인 dp 문제이다. 2로 나눈 수, 3으로 나눈 수, 1을 뺀 수에 대한 최소 계산 횟수를 안다면, 각각의 수에 해당하는 최소 계산 횟수에서 1만 더해주면 연산을 시행하기 전 수에서의 최소 계산 횟수를 구할 수 있다. 한마디로 n이라는 수를 입력받았을..

문제 설명 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000)가 주어진다. 입력으로 주어지는 모든 수는 정수이다. 출력 한 줄에 배낭에 넣을 수 있는 물건들의 가치합의 최댓값을 출력한다. 입력 예시 4 7 6 13 4 8 3 6 5 12 출력 예시 14 전형적인 dp 문제이다. 수업시간에도 배웠던 문제라 아주 쉽게 해결할거라 생각했는데... 아직 실력이 많이 부족한가보다ㅠㅠ 첨에 repetition이 가능한 문제인줄 알았는데.. 잘 읽어보면 알겠지만 이 문제는 repetition이 불가능한 0-1 kna..

문제 설명 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점수를 얻게 된다. 예를 들어 와 같이 시작점에서부터 첫 번째, 두 번째, 네 번째, 여섯 번째 계단을 밟아 도착점에 도달하면 총 점수는 10 + 20 + 25 + 20 = 75점이 된다. 계단 오르는 데는 다음과 같은 규칙이 있다. 계단은 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다. 즉, 한 계단을 밟으면서 이어서 다음 계단이나, 다음 다음 계단으로 오를 수 있다. 연속된 세 개의 계단을 모두 밟아서는 안 된다. 단, 시작점은 계단에 포함되지 않는다. 마지막 도착 계단은 반드시 밟아야 한다. 따라서 첫 번째 계..

첫째 줄부터 총 N개의 줄에 걸쳐 온라인 저지 회원을 나이 순, 나이가 같으면 가입한 순으로 한 줄에 한 명씩 나이와 이름을 공백으로 구분해 출력한다. 예제 입력 3 21 Junkyu 21 Dohyun 20 Sunyoung 예제 출력 20 Sunyoung 21 Junkyu 21 Dohyun 몰랐는데 파이썬 sort 함수는 시간복잡도가 O(nlogn)이라고 한다. 난 내가 스스로 merge sort나 quick sort 관련해서 함수를 짜야하나 싶었는데... 그런게 아니라 그냥 단순히 python sort 함수를 쓰면 되는거였다! (아주 쉬운 문제) 덕분에 sort 함수에서 key parameter 사용 방법을 다시 복습하는 계기가 되었다. n = int(input()) baek = [] for i in ..

개인적으로 코드가 깔끔하지는 않아서 마음에 안든다. 파이썬을 오랜만에 써봤더니 기초적인 코드임에도 불구하고 문법이 꽤 헷갈린다. 문제 제목이 너무 독특해서? 풀고 싶었다. 첫 번째 줄에 가장 많이 등장한 알파벳의 등장 횟수를 출력하는 단순한 문제였다. 다만, '띄어쓰기, 쉼표, 마침표는 세지 않는다.'는 조건을 읽지 않는 실수를 하지 않도록 조심하자. n = input() str = input() str_count = [] for i in str: if(i !=',') and (i != ' '): str_count.append(str.count(i)) print(max(str_count))