본문 바로가기

class 521

[백준 12852] 1로 만들기 2 [Python] 문제정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다.X가 3으로 나누어 떨어지면, 3으로 나눈다.X가 2로 나누어 떨어지면, 2로 나눈다.1을 뺀다.정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오.입력첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 자연수 N이 주어진다.출력첫째 줄에 연산을 하는 횟수의 최솟값을 출력한다.둘째 줄에는 N을 1로 만드는 방법에 포함되어 있는 수를 공백으로 구분해서 순서대로 출력한다. 정답이 여러 가지인 경우에는 아무거나 출력한다.풀이아래 문제의 확장판이다. [백준 01463] 1로 만들기 [C/C++]문제정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다.X가 3으.. 2024. 7. 22.
[백준 27172] 수 나누기 게임 [Java] 풀이 N명의 플레이어가 가진 카드에 대해서 서로 다른 플레이어의 카드 간 배수가 존재하는지 판별하는 문제다. 문제에서 두 번 이상 등장하는 카드는 없다고 하니 해당 번호의 카드의 존재여부를 기록해두면 쉽게 풀이할 수 있다. N명의 player에 대해 카드 번호를 입력받고 i번째 플레이어가 가진 카드가 있다고 표시해주자. 그 다음에는 N명의 player가 가진 카드의 배수에 해당하는 카드가 있는지 확인해주면 된다. 만약 카드 숫자가 i 일 때 카드 숫자가 j 인 카드가 있다면, j % i == 0 즉 j는 i의 배수다. 만약 최대 숫자 1,000,000 (SIZE - 1) 에 대해 i 배수를 탐색했는데 만족하는 카드가 없다면, i 카드를 가진 player는 점수를 얻을 수 없다. 점수를 score 배열에 .. 2023. 7. 13.
[백준 17404] RGB거리 2 [C] 풀이 "백준 1149, RGB거리"에 조건이 추가된 문제이다. 입력받은 비용들을 여러 번 사용해야 하고, 처음에 고른 색에 따라 최소비용을 계산해주어야 한다. 소스코드 #include #define MAX 1000001 #define MIN(a,b) (a < b ? a : b) int main(){ int N, result = MAX; scanf("%d", &N); int cost[N][3], min[3] = {0,}, old[3] = {0,}; for (int i = 0; i < N; i++) scanf("%d %d %d", &cost[i][0], &cost[i][1], &cost[i][2]); for (int i = 0; i < 3; i++){ old[0] = old[1] = old[2] = MAX;.. 2021. 9. 5.
[백준 14003] 가장 긴 증가하는 부분 수열 5 [C] 풀이 "백준 12015, 가장 긴 증가하는 부분 수열 2"에서 부분 수열의 최대 길이를 lower bound방식으로 빠르게 구했지만, 이렇게 만들어진 임의의 수열들의 요소가 최대 길이를 이루는 요소들이 아님을 예시를 통해 알 수 있었다. 한마디 더 붙이자면, 임시로 생성하는 수열의 최댓값보다 작은 경우에는 lower bound으로 찾은 index위치에 덮어쓰기 때문에 최대 길이를 이루는 요소가 아님을 알 수 있다. 만약 입력받은 요소들이 몇 번째 index에서 덮어쓰기가 되는지 알 수 있다면, 이전의 방법으로 구한 부분 수열의 최대 길이와, 입력받은 요소의 개수 N을 조건에 따라 줄여가면, 요소들을 구할 수 있다. 소스코드 #include #define MAX 1000001 int arr[MAX], te.. 2021. 9. 4.
[백준 12015] 가장 긴 증가하는 부분 수열 2 [C] 풀이 "백준 11053, 가장 긴 증가하는 부분 수열"보다 수열의 크기가 커, 기존의 방법대로 하면 시간초과가 발생한다. 수열 전체에서 binary search로 특정한 조건의 부분 수열을 탐색하는 방법은 아닌 것 같아 lower bound만을 이용했다. 다음과 같이 수열의 길이만을 계산하기 위해 다음과 같이 수열을 만들었다. i = 0이거나, 생성 중인 수열의 가장 뒷 값보다 큰 경우에는 길이를 늘려준다. 위의 조건이 아닐 때마다, lower bound로 적절한 위치에 입력받은 값을 삽입한다. 10 20 10 11 20 와 같은 수열을 입력 받았다고 가정하자. 앞에서 순차적으로 값이 커지는 경우만 계산을 한다면 10 20으로 최대 길이가 2다. 때문에, 11처럼 20보다는 작지만, 10보다는 큰 경우 .. 2021. 9. 4.
[백준 9466] 텀 프로젝트 [C] 풀이 n명에 대해서 각각 dfs을 해 만들어진 팀의 학생 수 만큼 전체에서 빼면 된다. 중복을 방지하기 위해, 팀을 짜기 시작한 경우(visited[0])와 탐색이 끝난 경우(visited[1])로 확인을 해주었다. 이전에 만난적 없는 번호이면 짝을 찾아가고, 만난적 있는 짝일 때, 그 짝의 탐색이 끝나지 않은 경우라면 순환이 가능한 즉 팀이 만들어 질 수 있다. 순환점을 발견하기 전 까지 재 탐색을 하며 개수를 세주고, 마지막에 자기 자신을 세어 주면 된다. 소스코드 #include #include #include #define MAX 100001 bool visited[2][MAX]; int arr[MAX], N, cnt; void dfs(int num, int depth){ if (!depth){ .. 2021. 9. 4.

티스토리툴바