Programming/BackJoon
-
10989 - 수 정렬하기Programming/BackJoon 2023. 4. 21. 14:37
https://www.acmicpc.net/problem/10989 10989번: 수 정렬하기 3 첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 10,000보다 작거나 같은 자연수이다. www.acmicpc.net 천만개를 정렬하려면 어떤 수를 써야할까 dict에 갯수를 표시하고 그 값만 출력하면 어떨까? -> 아마 이 방법이 계수정렬하고 비슷할듯하다. import sys t_case = int(sys.stdin.readline()) counting_lst = [0] * (10000+1) for i in range(0, t_case): v1 = int(sys.stdin.readline()) counting_lst[v1] += ..
-
11650 - 좌표 정렬하기Programming/BackJoon 2023. 4. 21. 14:06
https://www.acmicpc.net/problem/11650 11650번: 좌표 정렬하기 첫째 줄에 점의 개수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개의 줄에는 i번점의 위치 xi와 yi가 주어진다. (-100,000 ≤ xi, yi ≤ 100,000) 좌표는 항상 정수이고, 위치가 같은 두 점은 없다. www.acmicpc.net 튜플로 받고, 정렬하면 쉽게 푸는 문제 t_case = int(input()) lst = [] for i in range(t_case): x, y = input().split(' ') lst.append((int(x), int(y))) lst.sort(key=lambda x: (x[0], x[1])) for item in lst: print(i..
-
10814 -나이순 정렬Programming/BackJoon 2023. 4. 21. 14:03
https://www.acmicpc.net/problem/10814 10814번: 나이순 정렬 온라인 저지에 가입한 사람들의 나이와 이름이 가입한 순서대로 주어진다. 이때, 회원들을 나이가 증가하는 순으로, 나이가 같으면 먼저 가입한 사람이 앞에 오는 순서로 정렬하는 프로그램을 www.acmicpc.net 받은 입력을 나이순, 이름순으로 정렬한다. 문제 조건에 가입일순도 있긴해서 가입일을 정렬하려고했는데, 풀어보니 가입일 없이도 풀린다. 튜플이용해서 풀고, 리스트안에 튜플을 정렬할때 lambda를 사용할 줄 알면 금방 풀겠다 t_case = int(input()) lst = [] for i in range(t_case): age, name = input().split(' ') lst.append((int..
-
1427 - 소트인사이트Programming/BackJoon 2023. 4. 21. 13:46
https://www.acmicpc.net/problem/1427 1427번: 소트인사이드 첫째 줄에 정렬하려고 하는 수 N이 주어진다. N은 1,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net int 한개를 받아서 그 안의 수를 내림차순으로 정렬하면 끝나는 문제 숫자를 list로 변환하고, sort하고, print문에서 end='' 옵션을 줘서 풀었다. import sys lst = list(map(int, sys.stdin.readline().rstrip())) lst.sort(reverse=True) for i in lst: print(i, end='') 다른 사람들의 풀이도 보면 간단히 푼다. array = input() for i in range(9, -1, -1)..
-
11399 - ATMProgramming/BackJoon 2023. 3. 21. 08:15
1) 문제 설명 ATM은 1대이고, 각 사람마다 인출하는 시간이 있음 P1 = 3, P2 = 1, P3 = 4, P4 = 3, P5 = 2 1번째 사람은 인출하는데 3분, 두번째는 1분, 세번째는 4분.... 순서대로 인출할 경우에는 1번째 사람 3분 = 3분 2번째 사람 3분 + 1분 = 4분 3번째 사람 3분 + 1분 + 4분 = 8분 4번째 사람 3분 + 1분 + 4분 + 3분 = 11분 5번째 사람 3분 + 1분 + 4분 + 3분 + 2분 = 13분 총 39분이 걸림 그러나 대기시간이 짧은 순서대로 인출을 하면 32분안에 해결이 된다 그리디 문제로 제일 짧은거부터 선택해서 나아가면 될듯 하다. n = int(input()) lst = list(map(int, input().split())) lst..
-
2225 - 합분해Programming/BackJoon 2023. 3. 20. 14:07
1) 문제 설명 특정 수를 몇개로 만들 수 있는지 구하는 것 0도 허용되고, 중복이 허용되고, 여러번 사용도 가능 예를 들어서, n = 1이고, k = 2이면 -> 1을 0,1만 써서 만드는 방법의 수를 구해야한다. 0+1, 1+0 => 2가지 n=1이고, k=3이면, 3가지이다. n=1,k=2보다 1개가 더 늘어난다. 0+0+1, 0+1+0, 1+0+0 다른 경우를 따져보면, n = 2, k = 2이면 2를 만드는데, 0,1,2를 사용하는 경우를 찾는것 0+2, 2+0, 1+1 -> 3가지 n = 2, k = 3이면, 총 6가지가 나온다. 0+0+2, 0+2+0, 2+0+0, 0+1+1, 1+0+1, 1+1+0 표로 그려보면 더 쉽게 점화식이 보인다 가로축이 n이고, 세로가 k이다. (n을 k개의 숫자..
-
1699 - 제곱수의 합Programming/BackJoon 2023. 3. 17. 10:35
1) 문제 링크 https://www.acmicpc.net/problem/1699 1699번: 제곱수의 합 어떤 자연수 N은 그보다 작거나 같은 제곱수들의 합으로 나타낼 수 있다. 예를 들어 11=32+12+12(3개 항)이다. 이런 표현방법은 여러 가지가 될 수 있는데, 11의 경우 11=22+22+12+12+12(5개 항)도 가능하다 www.acmicpc.net 2) 문제 설명 어떤 자연수를 제곱수로 나타낼 수 있다 ex ) 11 = 3^2 + 1^2 + 1^2 -> 3개로 가능 3) 문제 풀이 처음에는 받은 수 n 의 sqrt를 구해서 해볼 생각이었다. (수학 + 구현 문제인줄..) 예를 들어서 11이면 int(math.sqrt(11)) = 3 11 - 3^2 = 2 int(math.sqrt(2))..
-
2579 - 계단 오르기Programming/BackJoon 2023. 3. 16. 13:58
1) 문제 설명 계단을 오르는 데 조건이 있다 계단은 한번에 한 계단 혹은 두 계단씩 오를 수 있다. 한 계단을 밝으면 그 다음 혹은 그 다음 다음 계단을 밟을 수 있다 연속된 세개 계단은 밟을 수 없다 마지막 계단은 반드시 밟아야 한다 2) 문제 이해 조건에 왜 마지막 계단을 밟아야 되는지를 주었는지 모르겠다 일단 dp 문제라고 이해하고, 규칙을 찾아본다 첫번째 계단은 밟거나 밟지 않을 수 있다. (2 계단을 건너뛸 수도 있으므로..) 두번째 계단은 첫번째 계단을 밟고, 또 밟을 수 있다. 그리고 두번째 계단만 밟을 수도 있다. 세번째 계단은 첫번째 계단을 밟고, 2칸을 건너뛴 다음에 세번째를 밟을 수 있고 2번째 계단을 밟고, 3번째 계단을 밟는 경우가 있다. 네번째부터는 점화식을 세울 수 있다 경우..