본문 바로가기

백준

 (43)
[C] 구슬 탈출2 백준 13460번 문제 스타트링크에서 판매하는 어린이용 장난감 중에서 가장 인기가 많은 제품은 구슬 탈출이다. 구슬 탈출은 직사각형 보드에 빨간 구슬과 파란 구슬을 하나씩 넣은 다음, 빨간 구슬을 구멍을 통해 빼내는 게임이다. 보드의 세로 크기는 N, 가로 크기는 M이고, 편의상 1×1크기의 칸으로 나누어져 있다. 가장 바깥 행과 열은 모두 막혀져 있고, 보드에는 구멍이 하나 있다. 빨간 구슬과 파란 구슬의 크기는 보드에서 1×1크기의 칸을 가득 채우는 사이즈이고, 각각 하나씩 들어가 있다. 게임의 목표는 빨간 구슬을 구멍을 통해서 빼내는 것이다. 이때, 파란 구슬이 구멍에 들어가면 안 된다. 이때, 구슬을 손으로 건드릴 수는 없고, 중력을 이용해서 이리 저리 굴려야 한다. 왼쪽으로 기울이기, 오른쪽으로..
[C] 달리기 백준 2517번 문제 문제 OI 장거리 달리기 대회가 진행되어 모든 선수가 반환점을 넘었다. 각 선수의 입장에서 자기보다 앞에 달리고 있는 선수들 중 평소 실력이 자기보다 좋은 선수를 남은 거리 동안 앞지르는 것은 불가능하다. 반대로, 평소 실력이 자기보다 좋지 않은 선수가 앞에 달리고 있으면 남은 거리 동안 앞지르는 것이 가능하다. 이러한 가정 하에서 각 선수는 자신이 앞으로 얻을 수 있는 최선의 등수를 알 수 있다. 각 선수의 평소 실력은 정수로 주어지는데 더 큰 값이 더 좋은 실력을 의미한다. 현재 달리고 있는 선수를 앞에서 부터 표시했을 때 평소 실력이 각각 2, 8, 10, 7, 1, 9, 4, 15라고 하면 각 선수가 얻을 수 있는 최선의 등수는 (같은 순서로) 각각 1, 1, 1, 3, 5,..
[C++] 게임 백준 1103번 게임 문제! 문제 형택이는 1부터 9까지의 숫자와, 구멍이 있는 직사각형 보드에서 재밌는 게임을 한다. 일단 보드의 가장 왼쪽 위에 동전을 하나 올려놓는다. 그다음에 다음과 같이 동전을 움직인다. 동전이 있는 곳에 쓰여 있는 숫자 X를 본다. 위, 아래, 왼쪽, 오른쪽 방향 중에 한가지를 고른다. 동전을 위에서 고른 방향으로 X만큼 움직인다. 이때, 중간에 있는 구멍은 무시한다. 만약 동전이 구멍에 빠지거나, 보드의 바깥으로 나간다면 게임은 종료된다. 형택이는 이 재밌는 게임을 되도록이면 오래 하고 싶다. 보드의 상태가 주어졌을 때, 형택이가 최대 몇 번 동전을 움직일 수 있는지 구하는 프로그램을 작성하시오. 입력 줄에 보드의 세로 크기 N과 가로 크기 M이 주어진다. 이 값은 모두 50..
[ICPC] Cosmetic Survey 백준 16358번으로 풀어본 Icpc 예선 문제 문제가 너무 길어서 읽기 싫었지만 문제 해석만 꼼꼼히 하면 의외로 쉬운 문제 input 크기가 작아서 3중 for문 까지 가능ㅎㅎ 문제가 복잡하니 조건을 정리해보자면 - 각 평가자들은 양의 정수로 rank를 주고 수가 적을수록 선호도가 높은 것이다 - rank는 유일하거나 연속하지 않다 - rank를 매기지 않았다면 선호도 우선순위에서 제외된다 각 사용자별 선호도를 입력 받은 후 d(X,Y)라는 notation에 맞추어 d 배열을 만들었다 이 배열은 X보다 Y를 확실히 선호하는 사람의 수이다 input 배열을 돌면서 각 사용자의 확실한 선호도가 존재하는 경우 d배열의 적절한 index를 증가시켜주었다 그다음 플로이드 와샬 알고리즘과 비슷하게 경유지를 정해서..
[ICPC] Rectilinear Regions 백준 14957번으로 풀어본 icpc 문제 u계단이 위에 있을 때 계단 사이의 공간 크기를 전부 구하는 문제였다 뭔가,,,이런 상황을 푸는 알고리즘이 있을 것 같은데 이론 공부가 부족해서 그냥 대충 해봐야지 하고 시작했다 생각은 되게 금방했는데 index 다루는데 실수가 많아서 오래 걸렸던 문제 바로 코딩 들어가지 말고 앞으로는 노트에 인덱스 정리하고 코딩 시작해야겠다ㅠㅠ 이런 순서로 움직이면서 rectilinear region의 개수와 넓이를 세었다 이 때 시작점과 끝점 처리하는곳에서 실수가 있었는데 시작점과 끝점은 음의 무한대, 양의 무한대로 생각하면 된다 그래서 두 계단이 교차 되고 나서야 왼쪽,오른쪽이 닫혀서 넓이로 셀 수 있다 계단의 시작점 말고 rectliner region이 만들어질 수 있는..
[ICPC] Philosopher’s Walk 백준 14956번을 통해 풀어본 icpc 예선 문제! input크기만 봐도 절대 다 채우는걸로는 안되겠다 싶었다 $ 2^{15}*2^{15} =2^{30} $ 까지 채워야하는 것에 그 전것도 저장해야하고.. 암튼 재귀로 나누어서 풀어보기로 했다 어떻게 풀기는 했지만 너무 노가다로 풀어서 시간도 꽤 많이 들었고 아쉽다 처음에 사분면으로 나누는 것은 쉽게 재귀로 구현했다 m 값을 그대로 쓰면 나머지 0일때 처리해주기가 까다로워서 -1을 해주고 시작했다 그렇게 사분면을 나누고 나눈 사분면에 따라 중심값을 이동시켜 주면서 좌표를 찾아내었다 처음에는 주어진 n값의 절반인 (n/2,n/2)가 중점이 되고 그 다음부터는 사분면에 따라 중점 결정! 여기서부터 노가다가 시작됐다ㅋㅋㅋ 이렇게 사분면 값을 0~3으로 나타내..
[ICPC] Parentheses 백준 16362번으로 풀어본 icpc 예선 문제 예전에 인턴 프로젝트 할 때 코드 tokenizer 만들면서 lex,yacc 쓰기 전에 아무것도 모르고 손수 코드를 작성한 적이 있었는데 그 생각하면서 코드 그냥 노가다로 작성해보았다 분명 재귀로 예쁘게 짤 수 있을 것 같은데 막상 짜려니까 코드가 잘 안나왔다ㅠㅠ 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 7..
[ICPC] Working Plan 백준 16368번으로 풀어본 icpc 문제 해결해야 할 일과 일들을 할 사람들이 존재하는 상황에서 일을 끝내기 위해 며칠에 몇시간의 일을 해야하는 지와 각 사람들이 총 몇시간 일할수 있는지가 주어진다 또한 사람들은 한번에 며칠을 연속으로 일해야하고 일한 후에는 며칠을 쉬어주어야한다 이 때 가능한 방법이 있으면 1과 어떻게 사람을 배치해야 하는지 없다면 -1을 출력해야한다 가능한 방법이 있는 경우 원래 일보다 추가로 일해도 되는지가 문제 해석 중 헷갈렸지만 고려하지 않아도 정답인정이 되었다 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44..

티스토리툴바