본문 바로가기

분류 전체보기

 (341)
[백준 / BOJ] 14720 우유 축제 문제 출처 www.acmicpc.net/problem/14720 14720번: 우유 축제 영학이는 딸기우유, 초코우유, 바나나우유를 좋아한다. 입맛이 매우 까다로운 영학이는 자신만의 우유를 마시는 규칙이 있다. 맨 처음에는 딸기우유를 한 팩 마신다. 딸기우유를 한 팩 마신 후�� www.acmicpc.net 영학이는 딸기우유 초코우유 바나나 우유를 좋아한다. 영학이는 가게를 지나가면서 우유를 먹을건데, 무조건 딸기우유 초코우유 바나나우유 순서로 먹어야한다. (초코우유를 먹지않고, 딸기우유만 먹었다면 바나나 우유를 먹지못한다.) 이때, 영학이가 먹을수있는 우유의 최대 갯수를 구하는문제다. 풀이 딸기우유 : 0, 초코유우 : 1, 바나나우유 : 2 라 할때 영학이가 우유를 먹기 시작할수있는 위치는 0이다.(..
[백준 / BOJ] 1405미친로봇 문제 출처 : www.acmicpc.net/problem/1405 1405번: 미친 로봇 첫째 줄에 N, 동쪽으로 이동할 확률, 서쪽으로 이동할 확률, 남쪽으로 이동할 확률, 북쪽으로 이동할 확률이 주어진다. N은 14보다 작거나 같은 자연수이고, 모든 확률은 100보다 작거나 같은 자�� www.acmicpc.net 로봇이 동, 서, 남, 북 4방향으로 N번 이동한다. N번 이동했을때, 방문한 지점을 한번 더 방문했다면 경로가 복잡하다고 하고, 아니라면 경로가 간단하다고 한다. 각 방향에 대한 확률과 이동하는 횟수가 주어졌을때, 로봇의 이동경로가 간단할 확률을 구하는 문제다. 풀이 DFS와 백트래킹으로 풀었다. 처음에는 입력받은 동, 서, 남, 북 만큼 전부 저장해주고 (25 25 25 25를 입력받으..
[백준 / BOJ] 11062 카드게임 문제 출처 : www.acmicpc.net/problem/11062 11062번: 카드 게임 근우와 명우는 재미있는 카드 게임을 하고 있다. N개의 카드가 일렬로 놓여 있다. 각 카드에는 점수가 적혀있다. 근우부터 시작하여 번갈아가면서 턴이 진행되는데 한 턴에는 가장 왼쪽에 있는 � www.acmicpc.net 근우와 명우는 카드게임을 하고있다. 근우부터 시작하여 번갈아가면서 카드를 선택하는데, 이때 서로가 최선의 전략으로 임할때 근우가 얻는 최대점수를 구하는문제다. (단, 남아있는 카드중 가장 오른쪽과 가장끝만 선택할수있다.) 풀이 어려웠던 문제였다. 서로가 항상 최선의 전략으로 임한다고 하는데, 어떤 걸 선택해야 최선의 상황이 되는지 모르기 때문에 모든경우를 다 봐줘야한다. 플레이어(근우와 명우)는 ..
[백준 / BOJ] 3213 피자 문제 출처 : www.acmicpc.net/problem/3213 3213번: 피자 첫째 줄에 친구의 수 N이 주어진다. (1 ≤ N ≤ 10,000) 다음 N개 줄에는 각 친구가 먹을 수 있는 피자의 양이 주어진다. 이 값은 항상 분수이며, 1/4, 1/2, 3/4중 하나이다. www.acmicpc.net 상근이의 친구들은 피자를 먹는데, 무조건 1/4, 3/4, 1/2크기만큼 먹을수있다. 이때, 상근이가 시켜야하는 최소한의 피자양을 구하는문제다. (1/4 3/4 1/2 만큼의 조각을 나눠서 먹는것이 아닌, 한번에 먹어야한다 ) 풀이 예제를 전부 더해보면 2가 나와서 2판만 시키면되는데, 출력은 3이나와서 뭔가했다... 알고보니 (번역본에는 안 나와있는데 본문에는 나와있음) 조각을 나눠서 먹으면 안되고..
[백준 / BOJ] 18512 점프 점프 문제 출처 : www.acmicpc.net/problem/18512 18512번: 점프 점프 첫째 줄에 두 사람이 한 번에 멀리뛰기를 하는 거리 X, Y와 시작 지점의 위치 값 P1, P2가 각각 공백을 기준으로 구분되어 자연수로 주어진다. (1 ≤ X, Y, P1, P2 ≤ 100) www.acmicpc.net 두 학생 A,B가 각각의 시작위치에서 출발하고 P1 P2만큼 움직일때, 가장 처음 만나게 되는 지점을 출력하는 문제다. 풀이 P1 P2에서 시작했을때 두 학생의 시작지점과 한번에 점프하는 거리가 학생끼리 서로소인지?? 판별해서 푸는문제 같았는데, X,Y,P1,P2의 최댓값이 100 이길래 완전탐색으로 풀어줬다. 계산해보지는 않았지만, 최댓값이 100밖에 안되므로, 10만번 돌았을때도 만나지 않는..
[백준 / BOJ] 19637 IF문 좀 대신 써줘 문제 출처 : www.acmicpc.net/problem/19637 19637번: IF문 좀 대신 써줘 첫 번째 줄에는 칭호의 개수 N (1 ≤ N ≤ 105)과 칭호를 출력해야 하는 캐릭터들의 개수 M (1 ≤ M ≤ 105)이 빈칸을 사이에 두고 주어진다. (1 ≤ N, M ≤ 105) 두 번째 줄부터 N개의 줄에 각 칭 www.acmicpc.net 게임 개발자 밀리는 캐릭터가 가진 전투력을 기준으로 칭호를 붙여주려고 한다. 캐릭터는 자신보다 큰거나 같은중에 가장작은수를 기준으로 칭호를 받는다 예를들어, 캐릭터의 전투력이 10이고 전투력이 10 보다 작거나같으면 A칭호를 받을때, A칭호를 받게된다. 풀이 칭호의 갯수가 100000 = 10만개 나올수있고 캐릭터의 수가 10만개 나올수있다. 따라서 완전..
[백준 / BOJ] 6146 신아를 만나러 문제 출처 : www.acmicpc.net/problem/6146 6146번: 신아를 만나러 키파는 신아를 만나러 아침 일찍(무려 6시에!) 일어났다. 간밤에 거센 비가 내려서 새로 산 장화를 신고 (0, 0)에 있는 집을 나선 키파는 무려 N(1 ≤ N ≤ 104)개의 웅덩이가 있는 것을 보고 놀랐다. www.acmicpc.net 키파는 신아에게 가야한다. 키파와 신아 사이에는 웅덩이가있고, 키파는 웅덩이를 피해서 가야한다.(키파가 신아에게 못가는경우는없다.) 키파의 위치는 항상 (0,0이고) 신아는 (-500~500, -500~500) 사이에 있다 키파는 상하좌우로만 움직일수있다. 풀이 BFS로 풀리는 문제였다. -500~500까지 가능하므로 전체 칸의 갯수는 1000 * 1000 = 1000000개..
[백준 / BOJ] 10423 전기가 부족해 (다익스트라) 문제 출처 : www.acmicpc.net/problem/10423 10423번: 전기가 부족해 첫째 줄에는 도시의 개수 N(1 ≤ N ≤ 1,000)과 설치 가능한 케이블의 수 M(1 ≤ M ≤ 100,000)개, 발전소의 개수 K(1 ≤ K ≤ N)개가 주어진다. 둘째 줄에는 발전소가 설치된 도시의 번호가 주어진다. 셋째 www.acmicpc.net K개의 발전소, N개의 도시, M개의 케이블수가 주어졌을때, 발전소에서 시작해서 모든도시까지 전기를 공급하는 문제다. 풀이 입력받은 발전소들을 시작지점으로해서 다익을 돌리면된다. 예를들어, 발전소가 3개일경우 다익의 시작지점은 총 3개가 된다. 코드를 짜면서 몇가지 반례?가 될수있는걸 생각해봤는데, 도시와 발전소 사이에 발전소가 존재할경우..? 발전소 N..

티스토리툴바