알고리즘 (39) 썸네일형 리스트형 [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] 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.. [ICPC] What’s Mine is Mine 백준 17979번으로 풀어본 icpc 지역 예선 문제 마지막 번호였던 L번 역시 문제 순서랑 난이도는 다르다 이 문제는 여러 종류의 광석이 있고 그 광석들을 채굴할 때 가장 돈을 많이 벌 수 있는 경우를 찾는 문제이다 이 때 광석을 캐서 벌 수 있는 돈은 광석이 나오는 (end time - start time) * price이다 DP로 풀면 될 것 같아서 먼저 DP 식을 세워보았다 DP[i] = i시간까지 채굴해서 얻을 수 있는 최대 금액 그리고 여기에 이전 값을 어떻게 활용할지에 대해 생각해보았다 현재 시간이 특정 광물의 end time일 때 그 광물의 start time의 DP값에서 이 광물을 더 한 것이 DP[i-1]보다 큰 지 확인해보았다 이 부분에서 실수를 해서 처음 풀이가 틀렸는데 특정 시간에.. [ICPC] Fire on Field 백준 17968번으로 풀어본 ICPC 지역 예선 문제 Let A[0] = 1, A[1] = 1. For a positive integer i ≥ 2, A[i] is the smallest positive integer under the condition that no three terms A[i − 2k], A[i − k], and A[i] form an arithmetic progression for any integer k > 0 such that i − 2k ≥ 0, that is, A[i] − A[i − k] ≠ A[i − k] − A[i − 2k]. 이러한 조건을 만족하는 배열에서 n번째 값을 찾는 문제이다 다 찾으면 이런식으로 분포가 된다고 한다 n의 범위가 1000까지밖에 안되길래 웬만한 풀.. [C++] 백준 5052번 : 전화번호 목록 문제 전화번호 목록이 주어진다. 이때, 이 목록이 일관성이 있는지 없는지를 구하는 프로그램을 작성하시오. 전화번호 목록이 일관성을 유지하려면, 한 번호가 다른 번호의 접두어인 경우가 없어야 한다. 예를 들어, 전화번호 목록이 아래와 같은 경우를 생각해보자 긴급전화: 911 상근: 97 625 999 선영: 91 12 54 26 이 경우에 선영이에게 전화를 걸 수 있는 방법이 없다. 전화기를 들고 선영이 번호의 처음 세 자리를 누르는 순간 바로 긴급전화가 걸리기 때문이다. 따라서, 이 목록은 일관성이 없는 목록이다. 입력 첫째 줄에 테스트 케이스의 개수 t가 주어진다. (1 ≤ t ≤ 50) 각 테스트 케이스의 첫째 줄에는 전화번호의 수 n이 주어진다. (1 ≤ n ≤ 10000) 다음 n개의 줄에는 목록.. 이전 1 2 3 4 5 다음
