본문 바로가기

알고리즘/백준

 (263)
[백준] 1106번 : 호텔 1106번: 호텔 1106번: 호텔 첫째 줄에 C와 형택이가 홍보할 수 있는 도시의 개수 N이 주어진다. C는 1,000보다 작거나 같은 자연수이고, N은 20보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 각 도시에서 홍보할 때 www.acmicpc.net 📄 문제개요 형택이가 홍보를 할 수 있는 도시가 주어지고, 각 도시별로 홍보를 하는데 드는 비용과, 그 때 몇명의 호텔 고객이 늘어나는지에 대한 정보가 있다. 단, 9원들 들여서 홍보하면 고객이 3명 늘어나는 조건에서 → 3원을 들여서 1명의 고객, 12원을 들려서 4명의 고객을 늘어나게 할수 없다. (9원 3명, 18원 6명, 27원 9명) 가능 호텔에 고객을 적어도 C명 늘리기 위해, 형택이가 투자해야 하는 돈의 최소값을 구하는 프로그램..
[백준] 2629번 : 양팔저울 2629번: 양팔저울 2629번: 양팔저울 첫째 줄에는 추의 개수가 자연수로 주어진다. 추의 개수는 30 이하이다. 둘째 줄에는 추의 무게들이 자연수로 가벼운 것부터 차례로 주어진다. 같은 무게의 추가 여러 개 있을 수도 있다. 추의 무 www.acmicpc.net 📄 문제개요 양팔 저울과 몇개의 추가 주어졌을때, 이를 이용하여 입력으로 주어진 무게의 구슬을 확인 할 수 있는지 결정하고자 한다. 제한된 추의 개수가 주어지고 ( 30개 이하 ), 추의 무게는 500g 이하이며, 구슬의 개수는 7개 이하이다. 각 구슬의 무게에 대하여 확인이 가능하면 Y 아니면 N을 출력한다. 양팔 저울에는 추를 둘다 놓을 수 있다. 🤔 문제분석 다이나믹 프로그래밍 현재의 추를 왼쪽으로 둔경우와, 오른쪽에 둔 경우 모두 갱신..
[백준] 2866번 : 문자열 잘라내기 2866번: 문자열 잘라내기 2866번: 문자열 잘라내기 첫 번째 줄에는 테이블의 행의 개수와 열의 개수인 R과 C가 주어진다. (2 ≤ R, C ≤ 1000) 이후 R줄에 걸쳐서 C개의 알파벳 소문자가 주어진다. 가장 처음에 주어지는 테이블에는 열을 읽어서 문자 www.acmicpc.net 📄 문제개요 R개의 행과 C개의 열로 주어진 테이블이 입력으로 주어진다. 이 테이블의 원소는 알파벳 소문자이다. 각테이블의 열을 위에서 아래로 읽어서 하나의 문자열로 만들 수 있다. 2 ≤ R, C ≤ 1000 🤔 문제분석 문자는 최대 1000개와 문자의 길이는 1000을 갖을 수 있다. 완전탐색의 경우 최악의 경우 O($N^3$)이다. 최악의 경우 1000번 반복하는데, 모든 문자의 중복을 확인( 1000 * 10..
[백준] 1920번 : 수 찾기 1920번: 수 찾기 1920번: 수 찾기 첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들 www.acmicpc.net 📄 문제개요 N개의 정수 A[1], A[2], …, A[N]이 주어져 있을때, 이 안에 X라는 정수가 존재하는지 알아내는 프로그램을 작성하시오. M개의 쿼리가 주어졌을때 해당 쿼리가 존재하면 1 존재하지 않으면 0을 출력하시오. 1≤ N ≤ 100,000, 1 ≤ M ≤ 100,000 -2^31 ≤ A[i] ≤ 2^31 🤔 문제분석 O(N*M)으로 완전탐색으로 해당값이 있는지 탐색 할 수 있다..
[백준] 10825번 : 국영수 [백준] 10825번 : 국영수 10825번: 국영수 10825번: 국영수 첫째 줄에 도현이네 반의 학생의 수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 한 줄에 하나씩 각 학생의 이름, 국어, 영어, 수학 점수가 공백으로 구분해 주어진다. 점수는 1보다 크거나 같고, 1 www.acmicpc.net 📄 문제개요 학생들의 이름과, 국어, 영어, 수학 점수가 주어졌을때, 다음과 같은 조건으로 성적을 정렬하는 프로그램을 작성하세요. 국어가 감소하는 순서로 국어 점수가 같으면 영어 점수가 증가하는 순서로 국어 점수와 영어점수가 같으면 수학점수가 감소하는 순서로 모든 점수가 같으면 사전 순으로 증가하는 순서로 (단, 아스키코드에서 대문자는 소문자보다 작으므로 사전 순으로 앞에 옵니다. ) 🤔 ..
[백준] 7453번 : 합이 0인 네 정수 [백준] 7453번 : 합이 0인 네 정수 7453번: 합이 0인 네 정수 7453번: 합이 0인 네 정수 첫째 줄에 배열의 크기 n (1 ≤ n ≤ 4000)이 주어진다. 다음 n개 줄에는 A, B, C, D에 포함되는 정수가 공백으로 구분되어져서 주어진다. 배열에 들어있는 정수의 절댓값은 최대 228이다. www.acmicpc.net 📄 문제개요 정수로 이루어진 크기가 같은 배열 A, B, C D 가 있다. A[a], B[b], C[c], D[d] 합이 0인 (a,b,c,d) 쌍의 개수를 구하는 프로그램을 작성하시오. 배열의 크기는 n ( 1≤ n ≤ 4000) 이고, 배열에 들어있는 정수 절대값은 최대 2^28이다. 🤔 문제분석 해당문제는 4000 x 4000 x 4000 x 4000 의 경우의 수..
[백준] 20058번 : 마법사 상어와 파이어스톰 [백준] 20058번 : 마법사 상어와 파이어스톰 https://www.acmicpc.net/problem/20058 20058번: 마법사 상어와 파이어스톰 마법사 상어는 파이어볼과 토네이도를 조합해 파이어스톰을 시전할 수 있다. 오늘은 파이어스톰을 크기가 2N × 2N인 격자로 나누어진 얼음판에서 연습하려고 한다. 위치 (r, c)는 격자의 r행 c www.acmicpc.net 📄 문제개요 2^Nx2^N인 격자로 나누어진 얼음판이 존재한다. 해당 얼음판에서 2^Lx2^L크기의 부분격자로 나눈뒤 모든 부분 격자를 시계 방향으로 90도 회전시킨다. 회전시킨후 각자의 위치에서 주변의 얼음이 3개 이하인경우 그자리에 있는 얼음을 녹인다. L 만큼 부분격자를 나누라는 명령이 Q번 주어진다. 출력으로는 첫재쭐에 ..
[백준] 2533번 : 사회망 서비스(SNS) 2533번: 사회망 서비스(SNS) 해당 문제는 노드를 방문해가면서 해당 노드가 얼리어뎁터일때와 얼리어뎁터가 아닐때에서의 최소값을 구하여 문제를 해결하면 된다. 자기자신이 얼리어뎁터가 아닌경우 - 친구들은 반드시 얼리어뎁터 이어야한다. 자기자산이 얼리어뎁터인경우 - 친구들은 얼리어뎁터가 아니거나 얼리어뎁터 일 수도 있다. 아래와 같은 점화식이 형성된다. 💡 dp[node][0] += dp[friend][1] 자기자신이 얼리어뎁터가 아닌경우 💡 dp[node][1] += min(dp[friend][1], dp[friend][0]] 자기자신이 얼리어뎁터인경우 import sys sys.setrecursionlimit(10 ** 9) N = int(input()) graph = [[] for _ in rang..

티스토리툴바