[백준] 1439번 - 뒤집기 1) 문제 해결 아이디어 아이디어는 쉽게 떠올렸다. 0과 1로만 이루어진 문자열에서 변화 횟수(cnt)를 세는 것이 포인트다. 예를 들어, 변화 횟수와 뒤집어야하는 최소 횟수는 다음과 같다. 문자열(s) 변화 횟수(cnt) 최소 뒤집기 횟수 0 0 0 01 1 1 010 2 1 0101 3 2 01010 4 2 (변화 횟수(cnt) + 1) // 2 가 최소 뒤집기 횟수이다. 2) 소스코드 s = input() # 0, 1로 구성된 문자열 cnt = 0 # 변화 횟수 for i in range(len(s) - 1): # 이전 숫자와 현재 숫자가 다를 경우 if(s[i] != s[i+1]): cnt += 1 print((cnt + 1) // 2)
[백준] 2875번 - 대회 or 인턴 (풀이1) 1) 문제 해결 아이디어 아이디어는 쉽게 떠올렸으나 탈출 조건을 세우는데 오류를 겪었다. 여학생 n명, 남학생 m인 총 n + m 명 중에서 k명은 인턴쉽에 참가해야한다. 한 팀은 2 : 1 로 구성되어 있기 때문에 while문 내에서 팀(team)을 1개 만들 때 마다 여학생(n)은 2명씩, 남학생(m)은 1명씩 뺀다. 하지만 n이나 m이 음수가 되거나 나머지 학생수(n+m)이 인턴쉽 참가인원(k)보다 작아질 경우, 현재 결성된 팀의 개수에서 1개를 뺸 후 탈출한다. 2) 소스코드 n, m, k = map(int, input().split()) team = 0 # 팀 수 while True: # 탈출 조건 if(n < 0 or m < 0 or n + m..
[백준] 1946번 - 신입 사원 1) 문제 해결 아이디어 처음에 제출했을 때는 시간초과로 실패했다. 시간 초과가 떴을 때는 input() 대신 sys.stdin.readline() 을 이용한다. 그런데도 시간초과가 떴다. 처음 생각한 방법은 일단 서류 순위 기준으로 오름 차순 정렬한다. (동석차는 없으므로 서류 기준으로만 정렬해도 된다.) 서류, 면접 둘 중 1개라도 1위인 지원자는 무조건 뽑힌다. 오름차순 정렬해놓았으므로 0번째 인덱스인 지원자는 자동 선발 처리하여 선발 인원 수(cnt)를 1로, 최고 면접 순위(high_rank)를 0번째 인덱스 지원자의 면접 순위로 초기화한다. 다음 인덱스인 1 ~ (n - 1)번째 리스트를 대상으로 for문을 돌린다. 선발이 되면 선발 인원수(cnt)를 변경하고..
[백준] 10610번 - 30 (풀이1) 정답 코드 1) 문제 해결 아이디어 해당 문제는 3의 배수임을 판별하는 조건을 알고 있으면 쉽게 풀 수 있는 문제였다. 배수 판별법에 따라 3의 배수는 각 자리의 숫자의 합이 3의 배수인 수이다. - 일의 자리수가 0 - 각 자리의 숫자들의 합이 3의 배수 일단 입력한 문자열을 리스트로 변환하여 내림차순 정렬하는 것이 포인트다. 30의 배수가 되는 조건 2개를 다 만족한다면 최댓값은 내림차순으로 정렬한 값이 될 것이다. [참고] https://m.blog.naver.com/PostView.naver?isHttpsRedirect=true&blogId=sctivcrmnfe&logNo=220859963688 3. (2,3,4,5,6,8,9) 배수 판별법 및 증명-1 기..
[백준] 1931번 - 회의실 배정 1) 문제 해결 아이디어 아이디어를 떠올리는 것은 꽤 쉬웠다. 입력받은 회의들을 끝나는 시간(1번 인덱스 값), 시작 시간(2번 인덱스값)을 기준으로 오름차순 정렬한다. 기본적으로 최대한 많은 회의를 하기 위해서는 끝나는 시간이 빠른 회의를 계속 진행시키는 것이다. 회의 시작 가능 시간(start)를 0으로 초기화한 상태로 시작한다. for문을 통해 회의 정보 리스트(info)의 회의들을 검사한다. 현재 회의 시작시간(i)가 시작 가능 시간(start) 이상의 값이라면 해당 회의를 진행할 수 있으므로 회의 개수(cnt)를 한 개 더한다. 추가적으로 다음 회의 시작 가능시간(start)를 현재 회의 끝나는 시간(j)로 업데이트 해주어야 한다. 코드 상에 주석처리된 arr..
[백준] 13458번 - 시험 감독 1) 문제 해결 아이디어 아이디어는 아주 쉽게 떠올렸는데, 검사해야할 조건문을 하나 빼먹어서 늪에 빠질 뻔했다. 각 시험장에 대한 응시자 수: arr, 총감독이 감시할 수 있는 응시자수: b 부감독이 감시할 수 있는 응시자수: c 각 시험장에는 총감독 1명을 필수로, 부감독은 응시자 수에 따라 여러명을 배치할 수 있다. 이 문제는 필요한 모든 감독 수의 최소값을 구하는 문제로 총감독 수는 어떻게 되든 각 시험장에 1명이므로 총 n명이 필요하다. (총 감독수는 시험장 개수에만 영향을 받음) 여기서 총 감독수는 일정하므로 전체 감독수를 최소로 만들기 위해 중요한 키포인트는 부감독수를 최소한으로 하는 것이다. i시험장에서 부감독이 관리해야할 총 응시자수는 (arr[i] - ..
[백준] 1541번 - 잃어버린 괄호 1) 문제 해결 아이디어 - 기준으로 괄호를 쳤을 때 최솟값이 된다. 60+20-50+10-20+30 이 입력으로 들어오면 (60+20)-(50+10)-(20+30) 이렇게 괄호를 쳤을 때 최소값이 된다. 상식적으로 최소값을 만들기 위해서는 큰 값으로 뺴주어야 하는데 - 기준으로 나누었기 때문에 괄호 ( ) 안에는 항상 숫자 혹은 더하기로만 이루어진 식이 오게 된다. 1. - 기준으로 분리한 결과 ["60+20", "50+10", "20+30"] 2. 각각을 + 기준으로 분리하고 int형 변환한 결과 [60, 20], [50, 10], [20, 30] 3. 첫번째 결과에서 나머지 결과들을 모두 뺀 결과 80 - 60 - 50 = -30 첫번째 괄호의 계산값에서 나머지..
[백준] 5585번 - 거스름돈 1) 문제 해결 아이디어 그리디 알고리즘의 대표적인 문제이다. for문에서 화폐단위가 큰 것부터 검사해야 총 동전 수의 최소값을 만들 수 있다. 2) 소스코드 pay = int(input()) # 지불 금액 money = [500, 100, 50, 10, 5, 1] charge = 1000 - pay # 잔돈 res = 0 # 잔돈 개수 for m in money: # 탈출 조건 if(charge == 0): break # 해당 단위로 나눠지면 if((charge // m) != 0): res += charge // m # 잔돈 개수 추가 charge %= m # 잔액 변경 print(res)
