멍두의 개발새발

📍 문제https://www.acmicpc.net/problem/1463 정수 N이 주어졌을 때 1. 3으로 나누거나2. 2로 나누거나3. 1로 빼서가장 적게 연산을 하여 1로 만드는 횟수를 구하는 문제이다. bfs로 /3 /2 -1해서 가장 빨리 1에 도착하는 방법으로도 풀 수 있을 것 같다.하지만 좀만 고민해본다면 dp로 풀 수 있고 dp가 시간 복잡도 깡패이므로 dp로 풀겠다.📍 코드 설명n=1일 때 : 0이다n=2일 때 : 2/2를 하면 1이므로 1이다n=3일 때 : 3/3을 하면 1이므로 1이다n=4일 떄 : 4/2 = 2, 2/2 = 1이므로 2이다n=5일 때 : 5-1 = 4, 4/2 = 2, 2/2=1 이므로 3이다n=6일 떄 : 6/3 = 2, 2/2 = 1이므로 2이다.n=7일 때 ..

📍 문제DP 문제이다.BFS로도 풀 수 있지만 bfs로 풀면 메모리초과로 실패가 뜬다..ㅠㅠ📍 코드 설명n번째 계단을 오르는 방법은 두가지이다n-1번째 -> n번째로 오르기 (연속 2계단)n-2번째 -> n번째로 오르기 (연속 1계단)dp[stairsNum + 1][2] 를 두어서 dp[n][1] -> n-2, n으로 올라온 값 / dp[n][2] -> n-1, n으로 올라온 값을 두어 최대 값을 구한다.dp[n][1] = Math.max(dp[n-2][1], dp[n-2][2]) + stairs[n]두칸 전에는 한칸 연속으로 와도되고, 두칸 연속으로 와도 되기 때문에 어떤 값이 최대인지 판단한다dp[n][2] = dp[n-1][1] + staris[n]두칸 연속에서는 반드시 1칸 연속으로 온 애만 ..

📍 문제https://www.acmicpc.net/problem/18110 상,하위 15퍼센트 의견은 제외하고 평균을 낸 뒤 반올림하는 문제쉬운 문제이지만 두 가지 방법으로 풀 수 있어서 글을 작성한다. 의견의 개수 n이 매우 크므로 이 부분에 유의 (0 ≤ n ≤ 3^105)📍 코드 설명첫번째 방법가장 떠올리기 쉬운 방법1. 의견을 배열에 받은 뒤 오름차순 정렬한다.2. 상 하 15%를 계산한다.3. 15%에 해당하는 index를 제외한 배열을 전부 더한 뒤 평균을 구한다 이 방법은 배열을 정렬할 때 평균 : O(nlog(n)) / 최악 : O(n^2),전부 더할 때 입력의 수만큼 돌아야한다. 두번째 방법countingSort를 이용한 방법1. 배열 index를 점수라 생각하고, 점수가 들어올때마다..

📍 문제https://www.acmicpc.net/problem/5525 I + OI이 n번 반복되는 문자열의 수를 찾으면 된다이때 주의할 점은 IOI을 찾을 때 IOIOI 은 1개가 아니라 IOIOI IOIOI 해서 2개이다 📍 코드 설명처음에 나는 i 이면 매번 뒤에 검사를 시작한다고 생각했는데 이러면 안된다. 시간초과가 나지 않기 위해선 최대한 내가 센 ioi를 기억하고 다시 활용해야 한다그렇다고 막 dp문제처럼 풀어야하는건 아니고 그냥 내가 센걸 이용해야만 시간초과가 나지 않는다는 것만 기억하면 된다. 1. i이면 검사를 시작2. oi이 몇번있는지 카운트3. 내가 원하는 개수만큼 잇다4. answer + 1 추가5. 만약 oi이 아니다 -> 다시 1번 부터 시작 이런 문자열 가지고 노는 문제에..

📍 문제https://www.acmicpc.net/problem/10814📍 코드 설명나이 순으로 정렬하고 나이가 같다면 먼저 입력된 순으로 정렬하는 문제이다. 두가지 방법으로 풀어볼수있다.1. class 를 이용하여 age, name을 입력받고 compareTo를 override하여 age순으로 정렬한다2. 배열 index로 age를 사용하여 나이와 이름을 저장한다.📍 코드✔️ class - compareTo 코드1. class로 Person을 만들어 age와 name을 변수로 가진다 2. Comparable의 compareTo를 구현한다.이때, 나이를 기준으로 정렬한다추후 출력에 용이하기 위해 출력 형식에 맞춰 ToString도 구현한다. 3. List으로 입력받고, Collection.sort..

📍 문제https://www.acmicpc.net/problem/9095📍 코드 설명입력 된 수를 1, 2, 3의 합으로 만들 수 있는 경우의 수를 세는 문제이다. 1, 2, 3이 합에서 이용되므로 일단 1, 2, 3을 만들 수 있는 경우의 수를 세보자 아직까지는 잘 모르겠으니 5까지 경우의 수를 구해보자 엇 이때 어떤 규칙을 알 수 있다 n=4를 자세히 보자 n=4일때 결국 n=3일때의 경우의 수에 + 1, n=2일때의 값에 + 2, n=1일때의 값에 + 3 을 하면 n=4의 경우의 수와 동일해진다 혹시모르니 n=5도 자세히 보자 여기서도 동일하게 n=4경우의 수에 +1, n=3의 경우의 수에 +2, n=2 의 경우의 수에 +3을 하면 n=5의경우의수가 나오는 것을 볼 수 있다. 이것으로 우리는 n..