본문 바로가기

분류 전체보기

 (340)
[백준 / BOJ] 3042 트리플렛 문제 출처 : www.acmicpc.net/problem/3042 3042번: 트리플렛 상근이와 창영이는 트리플렛이라는 게임을 하고 있다. 이 게임을 하려면 칠판에 N*N 그리드를 그려야 한다. 그 다음 알파벳 대문자를 적절히 각 칸에 써 넣는다. 한 알파벳을 여러 칸에 쓸 수는 �� www.acmicpc.net N*N그리드가 주어지고, 각 칸에 알파벳 혹은 '.'이 주어진다. 이때 3개의 알파벳이 한 직선을 이루면 이를 트리플렛 이라고 한다. 예를들어, ...A ..B. .C.. D... 은 ABC가 하나의 트리플렛을 이룬다, BCD가 트리플렛을 이룬다... 라고 생각하면된다. 풀이 그냥 완전탐색을 할경우, N이 최대 100이고 N*N이므로, 칸의 총 갯수는 100*100 = 10000개이다. 여기서 ..
[백준 / BOJ] 8901 화학 제품 문제 출처 : www.acmicpc.net/problem/8901 8901번: 화학 제품 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 두 줄로 이루어져 있다. 첫째 줄에는 상근이가 가지고 있는 A, B, C의 양이 주어진다. 둘째 줄에는 AB, BC, CA의 가격이 주어진다. www.acmicpc.net 상근이는 세 종류의 화학물질 A, B, C를 가지고 있다. 화학물질을 AB, BC, CA로 조합해서 세가지 제품을 만들수있는데, A,B,C의 갯수와 AB,BC,CA의 가격이 주어졌을때, 상근이가 얻는 최대이익을 출력하는 문제다. 풀이 완전탐색으로 풀리는문제다. 하지만, 그냥 모든경우를 봐줄경우, 1000 * 500 * 250 * 250 ?? 처럼 나와서 시간초과가 난다. 한가지 제..
[백준 / BOJ] 15658 연산자 끼워넣기 (2) 문제 출처 : www.acmicpc.net/problem/15658 15658번: 연산자 끼워넣기 (2) N개의 수로 이루어진 수열 A1, A2, ..., AN이 주어진다. 또, 수와 수 사이에 끼워넣을 수 있는 연산자가 주어진다. 연산자는 덧셈(+), 뺄셈(-), 곱셈(×), 나눗셈(÷)으로만 이루어져 있다. 연산자의 개수� www.acmicpc.net N개의 수가 주어지고, +, -, *, /연산자의 갯수가 주어진다. 이때, N개의 수와 연산자들로 만들수있는 조합중 최댓값과 최솟값을 찾는문제다. (단, 주어진 수의 순서를 꾸면 안된다.) 풀이 백트래킹을 이용한, 구현문제다. 연산자와 숫자를 전부 사용하지않고도 최댓값, 최솟값이 나올수있다는 조건을 주의하면서 코딩하자. ope[i] = 연산자 사용가능 ..
[백준 / BOJ] 2313 보석 구매하기 출처 풀이 : www.acmicpc.net/problem/2313 2313번: 보석 구매하기 첫째 줄에 정수 n(1 ≤ n ≤ 1,000)이 주어진다. 다음 2×n개의 줄에는 n개의 줄에 나열된 보석들에 대한 정보가 주어진다. 먼저 각 줄에 나열된 보석의 개수 L(1 ≤ L ≤ 1,000)이 주어지고, 그 다음 줄에 www.acmicpc.net 보석가게에 보석이 여러줄에 걸쳐 진열되어있다. 각각의 보석은 정수로 표현된다. 이때 음수도 나올수있다. 보석은 연속해서 구매할수있는데, 1 2 3을 구매할수있지만, 1 3 을 구매하지 못한다. 보석 가치의 총합이 최대가 될때를 찾아는 문제다. 풀이 한줄당 최대 1000개의 보석이 있을수있고, 최대 1000개의줄이 나올수있다. 따라서 최대 보석은 1000000개 만..
[백준 / BOJ] 12933 오리 문제 출처 : www.acmicpc.net/problem/12933 12933번: 오리 첫째 줄에 영선이가 녹음한 소리가 주어진다. 소리의 길이는 5보다 크거나 같고, 2500보다 작거나 같은 자연수이고, 'q','u','a','c','k'로만 이루어져 있다. www.acmicpc.net 오리의 울음소리는 quack이다. 'q', 'u', 'a', 'c', 'k'로 이루어진 문자열이 주어졌을때, 존재할수있는 오리의 최소수를 구하는 문제다. 풀이 구현문제다. 가능한 최소한의 오리 수를 구해야하므로, 'q'를 만났을때부터 시작해서 오리의 울음(quack)을 만들때마다 각 문자열 위치를 체크해준다. 한 오리를 최대한 많이 울게하면 된다. 예를들어, 울음소리가 quqacukqauackck로 주어졌다면 0번 인덱..
[백준 / BOJ] 5635 생일 문제 출처 : www.acmicpc.net/problem/5635 5635번: 생일 어떤 반에 있는 학생들의 생일이 주어졌을 때, 가장 나이가 적은 사람과 가장 많은 사람을 구하는 프로그램을 작성하시오. www.acmicpc.net 각 학생이 이름 년도 월 날짜 로 주어질때, 가장 나이가 많은 학생의 이름, 가장 나이가 적은 학생의 이름을 출력하는 문제다. 풀이 pair로 선언하고 오름차순 정렬하면 끝나는 문제다. vector vec; 처럼 선언하고 {{년도, 월},{날짜, 이름}}이 들어갔을때, 이를 오름차순 정렬하면, 1. 빠른년도순으로 2. 년도가 같으면 3. 빠른 월 순으로 4. 월이 같다면 빠른 날짜 순으로 자동 정렬해준다. 각 벡터의 끝과 시작을 출력하면 된다. 소스코드 https://gith..
[백준 / BOJ] 13931 숨바꼭질 4 문제 출처 : www.acmicpc.net/problem/13913 13913번: 숨바꼭질 4 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 �� www.acmicpc.net 수빈이와 동생은 숨바꼭질을 한다. 수빈는 자신의 위치에서 -1, +1, *2만큼 이동할수있다. 수빈이가 동생을 가장빨리 찾는 시간을 구하는 문제다. 풀이 BFS를 통해 푸는 문제였다. 배열을 이용해 자신의 전 위치를 체크해줘야하는데, 예를들어, 배열이 par[100005]로 선언되어있고 수빈이가 동생에게 가는 경로가 5 10 20 40 이라면, par[40]..
[백준 / BOJ] 11067 모노톤 길 문제 출처 : www.acmicpc.net/problem/11067 11067번: 모노톤길 입력 데이터는 표준입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 테스트 데이터의 개수 T가 정수로 주어진다. 각 테스트 데이터의 첫 번째 줄에는 카페의 수 www.acmicpc.net 산책코스가있다. 산책코스에는 코너마다 카페가있고, 코스관리자인 김씨는 산책로를 따라갈때 (X,Y)에있는 카페를 몇번째로 방문하는지 알고싶다. n개의 카페 위치(X,Y)가 주어졌을때 카페를 몇번 반복하는지 찾는 문제다. 단, X를 줄일필요없이 항상 모든카페를 방문할수있고, 같은 번호를 갖는 카페는 없다. 모든 코너에서는 90도로 회전해서 이동만할수있다.(대각선 이동이 안됨.) 풀이 우선, 제한시간이 ..

티스토리툴바