본문 바로가기

분류 전체보기

 (340)
[백준 / BOJ] 2872 우리집엔 도서관이 있어 문제 출처 : www.acmicpc.net/problem/2872 2872번: 우리집엔 도서관이 있어 상근이는 컴퓨터 공학의 일인자가 되기 위해 책을 매우 많이 구매했다. 하지만, 집에 책장이 없어서 책을 탑처럼 쌓아놓고 있다. 오늘은 오랜만에 상근이가 집에서 휴식을 취하는 날이다. 상근 www.acmicpc.net 상근이가 책을 정리할려고한다. 책은 1 2 3 4 5 ... N 순서대로 정리해야한다. 책을 정리하는 방법은 임의의 책 한권을 뽑아서 가장 앞에 놓는다. 최소 몇번의 이동으로 책을 정리할수있는지 출력하는 문제다. 풀이 i번째 책이 i+1번째 책보다 낮은위치에 존재하는지 확인해주며 풀면 되는 문제다. 예를들어, 9 1 2 3 4 5 7 6 8 9 의 책이 있다고 하자. (9번은 움직이지 않아도..
[백준 / BOJ] 2174 로봇 시뮬레이션 문제 출처 : www.acmicpc.net/problem/2174 2174번: 로봇 시뮬레이션 첫째 줄에 두 정수 A, B가 주어진다. 다음 줄에는 두 정수 N, M이 주어진다. 다음 N개의 줄에는 각 로봇의 초기 위치(x, y좌표 순) 및 방향이 주어진다. 다음 M개의 줄에는 각 명령이 명령을 내리는 순 www.acmicpc.net 로봇의 위치와 각 명령이 주어졌을때, 시뮬레이션을 안전하게 돌릴수 있는지 확인하는 문제다. 명령은 다음 3개가 있다. L: 로봇이 향하고 있는 방향을 기준으로 왼쪽으로 90도 회전한다. R: 로봇이 향하고 있는 방향을 기준으로 오른쪽으로 90도 회전한다. F: 로봇이 향하고 있는 방향을 기준으로 앞으로 한 칸 움직인다. 로봇이 명령을 수행하다가 다른로봇 혹은 벽과 충돌할경우..
[백준 / BOJ] 19942 다이어트 문제 출처 : www.acmicpc.net/problem/19942 19942번: 다이어트 식재료 N개 중에서 몇 개를 선택해서 이들의 영양분(단백질, 탄수화물, 지방, 비타민)이 일정 이상이 되어야 한다. 아래 표에 제시된 6가지의 식재료 중에서 몇 개를 선택해서 이들의 영양분의 각 www.acmicpc.net 식재료 N개중 몇개를 선택해서 이들의 영양분(단백질 탄수화물 지방 비타민)이 일정이상이 되어야한다. 각 식재료에는 가격이있다. 이때, 가격을 최소로하는 식재료 조합을 찾는 문제였다. 풀이 완전탐색으로 풀은 문제다. 탐색마다 영양소를 선택하는 경우, 선택하지 않는경우로 총 2가지 선택지가 있으므로, 최대 반복횟수는 2^15가 된다. 풀이는 간단한데, 단백질 탄수화물 지방 비타민 이 있을때, 각각의..
[백준/BOJ] 11560 다항식 게임 문제 출처 : www.acmicpc.net/problem/11560 11560번: 다항식 게임 매 테스트 케이스마다 한 줄에 걸쳐 다항식 \(p(x) = (1+x)(1+x+x^2)(1+x+x^2+x^3)\dots(1+x+\dots+x^{k-1}+x^k)\)의 \(x^N\)항의 계수를 출력한다. www.acmicpc.net k에 따라 다항식이 연결된다. k = 0 (1) k = 1 (1)(1+x) k = 2 (1)(1+x)(1+x+x^2) k = 3 (1)(1+x)(1+x+x^2)(1+x+x^2+x^3) . . . k = ? 일때의 다항식을 계산한 결과에서 N차항의 계수를 출력하는 문제다. 풀이 k = 20 , N = 210까지 간다. k가 늘어남에따라, 곱해야하는 항의 차수 또한 매우 늘어나므로, 완탐으..
[백준 / BOJ] 15906 변신 이동 게임 문제 출처 : www.acmicpc.net/problem/15906 15906번: 변신 이동 게임 첫 줄에 2차원 격자의 크기 N(1≤ N ≤ 500), 일반 모드에서 변신 모드로 변신하는 데 소모되는 턴의 수 t(0 ≤ t ≤ 500), 목표 지점의 행과 열의 번호 r(1 ≤ r ≤ N), c(1 ≤ c ≤ N)가 주어진다. 다음 줄에 www.acmicpc.net 성호는 새로운 모바일 게임을 다운로드 했다. 성호의 캐릭터는 N*N의 위치에서 상,하,좌,우로 1칸 움직일수있는데, 이때, 캐릭터가 변신모드라면, 상,하,좌,우중 가장 가까운 워프지점으로만 갈수있다. (변신모드로 전환하는데는 t만큼의 턴이 소요된다.) 성호의 캐릭터가 목표지점까지 도달하는데 걸리는 최소한의 턴을 구하는문제다. 풀이 다익스트라로..
[백준 / BOJ] 9663 N-Queen 문제 출처 : www.acmicpc.net/problem/9663 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net N*N의 체스판에 N개의 퀸을 서로 공격할수없도록 배치해야한다. 이때, 퀸을 놓는 경우의 수를 구하는 문제다. 풀이 N의 최댓값이 15이다. 따라서, 최악의경우 15 * 15의 판에 15개의 퀸을 놓는 경우이므로, 15! * 15^3 만큼 반복하게된다. 따라서, 모든경우를 봐줄려하면 시간초과가 나게된다. 시간초과를 피하기 위해서 체크배열을 이용해서 해당 위치에 퀸을 놓을수있는지 없는지 봐줘야한다. 퀸은 가로 세로..
[백준 / BOJ] 20046 Road Reconstruction 문제 출처 : www.acmicpc.net/problem/20046 20046번: Road Reconstruction 입력은 표준입력을 사용한다. 첫 번째 줄에 도시를 표현하는 격자의 행과 열의 크기를 각각 나타내는 두 개의 양의 정수 m, n (1 ≤ m, n ≤ 1,000, 1 < m×n)이 주어진다. 다음 m개의 각 줄에 격자의 각 � www.acmicpc.net m*n의 격자 모양의 격자가 있다. 격자의 각 칸에는 도로가 있을수도, 없을수도 있는데, 이 격자에 도로를 배치하여 (1,1)지점에서 (m,n)까지 가는 다리를 만들어야한다. 칸마다 도로를 만드는데 드는 비용은 다르다 (비용 1과 비용2가 있음) -1인 지점에는 도로를 만들지 못하고, 0은 이미 도로가 있는 곳이다. 비용을 최소한으로 사용..
[백준 / BOJ] 14720 우유 축제 문제 출처 www.acmicpc.net/problem/14720 14720번: 우유 축제 영학이는 딸기우유, 초코우유, 바나나우유를 좋아한다. 입맛이 매우 까다로운 영학이는 자신만의 우유를 마시는 규칙이 있다. 맨 처음에는 딸기우유를 한 팩 마신다. 딸기우유를 한 팩 마신 후�� www.acmicpc.net 영학이는 딸기우유 초코우유 바나나 우유를 좋아한다. 영학이는 가게를 지나가면서 우유를 먹을건데, 무조건 딸기우유 초코우유 바나나우유 순서로 먹어야한다. (초코우유를 먹지않고, 딸기우유만 먹었다면 바나나 우유를 먹지못한다.) 이때, 영학이가 먹을수있는 우유의 최대 갯수를 구하는문제다. 풀이 딸기우유 : 0, 초코유우 : 1, 바나나우유 : 2 라 할때 영학이가 우유를 먹기 시작할수있는 위치는 0이다.(..

티스토리툴바