요세푸스 순열이 대체 무슨 규칙으로 정해지는 지 감도 안잡혔음. 맨처음에는 N을 기준으로 양 끝의 수를 더해서 N이 되도록해야하나? 예를 들어서 이면 3+4 = 7, 6+1 = 7, 2+5 = 7 했는데 그러면 3, 6, 2 이 순서는 어떻게 만들어질지 모름. 문제를 잘 보면 " 한 사람이 제거되면 남은 사람들로 이루어진 원을 따라 이 과정을 계속해 나간다."이게 포인트였던 거 같다. 한 사람이 제거되면 제거된 사람을 제외한 새로운 길이를 기준으로 삭제할 사람을 찾아내야 했다. 풀이과정 1. 입력으로 주어진 k의 인덱스가 어디있는 지 찾는다. 2. 제거한 사람의 인덱스를 새로운 배열에 저장하고 기존 리스트에서는 삭제. 3. k번째 사람이 제거된 리스트의 길이로 재조정하고, (기존 배열에서의 k번째 사람의..
알고리즘/백준
수학적?으로 접근해서 매우 복잡하게 해석했다.. 좌표로 생각하면서 푸니까 서로 겹치는 부분을 찾기 위해 좌표가 주어지면 해당 좌표가 다른 좌표와 겹치는 지, 아닌지 검사하기 위해 조건문으로 다 걸러서 찾아냄 1차 시도 import java.io.*; import java.util.*; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); long s = 0; int n = Integer.parseInt(br.readLine()); int[][] lst = new int[n][2]; fo..
d(n)이라는 함수를 만들어서 리스트에 셀프넘버가 아닌 것들을 저장하자 라는 생각으로 접근 시도1 lst = [] def d(n): #셀프넘버가 아닌 것들 num = n + int(n/1000) + int(n%1000/100) + int(n%100/10) + n%10 return num n=0 while(True): n += 1 if d(n) > 10000: break lst.append(d(n)) for i in range(1, 10001): if i not in lst: print(i) 아무리 생각해도 맞는거 같은데 자꾸 출력이 이상하게 나와.... 그래서 왜 이상한지 손으로 노가다로 풀어봤다 저 코드를 실행하면 9999가 출력되는데 n = 9972일때 d(n) = 9999를 반환 하지만 내 코드에서..
처음에 재귀함수로 풀이 하지만 재귀함수로 하면 겹치는 계산이 존재해서 다른 풀이도 찾아보았다. import sys def fibo(n): if n == 0: return 0 elif n
처음에 간단하게 그냥 5로나누고 나머지를 2로 나눠서 나눠떨어지지 않으면 -1출력하면 되는거 아닌가? 했지만 당연히 아니다. 거스름돈이 13원인 경우 5원 한개 2원 4개로 거스름돈을 거슬러 줄 수 있다. 그럼 어떻게 해야할까? 최소한의 동전 개수로 거스름돈을 거슬러 줘야하므로 먼저 5로 나눠주고 cnt= 거스름돈 / 5 저장하고, 나머지 = n % 5 나머지가 2로 나눠지지 않는다면 나머지 += 5로 5원을 회수하고 cnt -= 1을 해준다. (동전 회수 했으므로 cnt도 감소해야함) 그리고 다시 5를 더한 나머지가 2로 나눠지는지 확인.... 위 과정 반복하다가 나머지에 계속 +5를 하다보면 주어진 거스름돈의 값을 넘기는 경우에는 -1을 출력하고 프로그램 종료 import java.util.*; im..
완전 탐색으로 첨탑 높이 비교 시도1 import java.util.*; import java.io.*; public class Main{ public static void main(String[] args) throws IOException { //첨탑 개수 완전 탐색 BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(br.readLine()); int n = Integer.parseInt(st.nextToken()); int[] data = new int[n]; st = new StringTokenizer(br.readLine()); for (in..
1차 시도 import sys n = int(input()) lst = [0] * n idx = 0 b = True for _ in range(n): i, j = sys.stdin.readline().rstrip().split() for k in i: if k not in j: lst[idx] = -1 idx += 1 b = False break if b: b = True idx += 1 for i in lst: if i == -1: print("Impossible") else: print("Possible") not in을 사용해서 첫번째 문자열을 하나씩 뜯어서 두번째 문자열에 문자가 포함되는지 확인. 포함 안되면 lst에 테스트 케이스대로 인덱스를 설정(테스트 케이스가 첫번째이면 idx=0)해서 -1..
1차 시도 2점 import sys n, k = map(int, input().split()) data = [tuple(map(int, sys.stdin.readline().rstrip().split())) for _ in range(n)] idx = 0 data = sorted(data, key= lambda x:(x[0], x[1])) for i in range(n): if data[i][0] == 1: idx = i #남학생 시작 idx break w_lst = data[:idx] m_lst = data[idx:] w_grade = [] m_grade = [] for i in w_lst: w_grade.append(i[1]) for i in m_lst: m_grade.append(i[1]) cnt ..
1 ≤ n ≤ 100000, 1 ≤ x ≤ 2000000 n은 입력받은 수열, x는 두 수열의 합 메모리 128MB 데이터의 개수가 1,000만 단위가 넘어가지 않도록... 1. itertools 라이브러리 사용해서 combination을 만들어서 x를 만드는 조합 개수를 찾자 -> 메모리 초과 (최대 10만 수열에서 2개 원소로 조합을 만들어서 리스트에 저장하면 대략 50억 가량의 데이터가 나옴.... from itertools import combinations import sys n = int(sys.stdin.readline().rstrip()) data = list(map(int, sys.stdin.readline().rstrip().split())) x = int(sys.stdin.readli..
