c++ (9) 썸네일형 리스트형 [C++] 특정한 최단 경로 백준 1504번 다익스트라를 응용한 문제였다 최단 경로는 경로인데 특정한 두 지점을 꼭 지나간 최단 경로 찾기 따라서 최단 경로를 저장하는 배열을 한 지점만 들른 경우, 두 지점 모두 들른 경우 나누어서 만들어주었다 예전에 비슷한 문제를 푼 적 있어서 dist 배열을 다차원 배열로 status 별로 나누는 것은 금방했지만 조건 체크에서 실수를 해서 몇번 틀렸다 꼭 들러야하는 점이 1인 경우 시작점이 1이라 자동적으로 들르게되지만 처음의 코드에서는 해당 케이스를 잡지 못했다 start status를 만들어 시작점이 1인 경우를 따로 체크해주었더니 정답처리되었다 최단 경로를 상황별로 나누어 저장하는 것과 시작점이 특정 지점인 경우만 체크해주면 될 듯한 문제! 1 2 3 4 5 6 7 8 9 10 11 12 .. [C++] 벽 부수고 이동하기 백준 2206번 solved ac 클래스 3이 끝나서 클래스 4 문제들을 풀기 시작했다 한참 많이 풀었던 bfs 유형이라 금방 풀 수 있었다 먼저 문제에서 요구하는 최단경로라는 키워드를 통해 bfs를 쓰면 되겠다고 판단했다 그 다음 벽을 단 한번만 부술 수 있으니 벽을 이미 부순 상태인지, 앞으로 부술 수 있는지만 나누어주었다 visit 배열 또한 벽을 부순 상태로 방문한 것인지, 부수지 않고 방문했는지 따로 저장했다 반복문 안에서의 조건은 아래와 같이 세가지로 나누었다 1. 벽도 없고 방문한 적도 없으며 앞으로 벽을 부술 수 있다 2. 벽이 없고 이미 벽을 부수었고 벽을 부순 상태로는 처음 방문한다 3. 벽이 있고 아직 벽을 부수지 않았다 이때 벽을 부순 칸을 다시 방문하는 것은 최단 경로가 아닌것이 .. [프로그래머스] 2021 Dev-matching : 웹 백엔드 개발자 풀이 데브매칭 문제가 공개되었길래 풀어보았다 이 날 라인 코테였나...? 날짜가 겹쳐서 하나만 나가느라 데브매칭은 신청 못했는데 문제가 공개되다니!! 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 #include #include using namespace std; int get_rank(int i){ if(i>=6) return 1; else if(i==5) return 2; else if(i==4) return 3; else if(i==3) return 4; else if(i==2) return 5; else return 6; } vector solution.. [C++] 게임 백준 1103번 게임 문제! 문제 형택이는 1부터 9까지의 숫자와, 구멍이 있는 직사각형 보드에서 재밌는 게임을 한다. 일단 보드의 가장 왼쪽 위에 동전을 하나 올려놓는다. 그다음에 다음과 같이 동전을 움직인다. 동전이 있는 곳에 쓰여 있는 숫자 X를 본다. 위, 아래, 왼쪽, 오른쪽 방향 중에 한가지를 고른다. 동전을 위에서 고른 방향으로 X만큼 움직인다. 이때, 중간에 있는 구멍은 무시한다. 만약 동전이 구멍에 빠지거나, 보드의 바깥으로 나간다면 게임은 종료된다. 형택이는 이 재밌는 게임을 되도록이면 오래 하고 싶다. 보드의 상태가 주어졌을 때, 형택이가 최대 몇 번 동전을 움직일 수 있는지 구하는 프로그램을 작성하시오. 입력 줄에 보드의 세로 크기 N과 가로 크기 M이 주어진다. 이 값은 모두 50.. [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]보다 큰 지 확인해보았다 이 부분에서 실수를 해서 처음 풀이가 틀렸는데 특정 시간에.. [C++] 백준 17471번 : 게리맨더링 문제 백준시의 시장 최백준은 지난 몇 년간 게리맨더링을 통해서 자신의 당에게 유리하게 선거구를 획정했다. 견제할 권력이 없어진 최백준은 권력을 매우 부당하게 행사했고, 심지어는 시의 이름도 백준시로 변경했다. 이번 선거에서는 최대한 공평하게 선거구를 획정하려고 한다. 백준시는 N개의 구역으로 나누어져 있고, 구역은 1번부터 N번까지 번호가 매겨져 있다. 구역을 두 개의 선거구로 나눠야 하고, 각 구역은 두 선거구 중 하나에 포함되어야 한다. 선거구는 구역을 적어도 하나 포함해야 하고, 한 선거구에 포함되어 있는 구역은 모두 연결되어 있어야 한다. 구역 A에서 인접한 구역을 통해서 구역 B로 갈 수 있을 때, 두 구역은 연결되어 있다고 한다. 중간에 통하는 인접한 구역은 0개 이상이어야 하고, 모두 같은 .. [C++] 백준 3190번 : 뱀 문제 'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다. 게임은 NxN 정사각 보드위에서 진행되고, 몇몇 칸에는 사과가 놓여져 있다. 보드의 상하좌우 끝에 벽이 있다. 게임이 시작할때 뱀은 맨위 맨좌측에 위치하고 뱀의 길이는 1 이다. 뱀은 처음에 오른쪽을 향한다. 뱀은 매 초마다 이동을 하는데 다음과 같은 규칙을 따른다. 먼저 뱀은 몸길이를 늘려 머리를 다음칸에 위치시킨다. 만약 이동한 칸에 사과가 있다면, 그 칸에 있던 사과가 없어지고 꼬리는 움직이지 않는다. 만약 이동한 칸에 사과가 없다면, 몸길이를 줄여서 꼬리가 위치한 칸을 비워준다. 즉, 몸길이는 변하지 않는.. [C++] 백준 10026번 : 적록색약 문제 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록), B(파랑) 중 하나를 색칠한 그림이 있다. 그림은 몇 개의 구역으로 나뉘어져 있는데, 구역은 같은 색으로 이루어져 있다. 또, 같은 색상이 상하좌우로 인접해 있는 경우에 두 글자는 같은 구역에 속한다. (색상의 차이를 거의 느끼지 못하는 경우도 같은 색상이라 한다) 예를 들어, 그림이 아래와 같은 경우에 RRRBB GGBBB BBBRR BBRRR RRRRR 적록색약이 아닌 사람이 봤을 때 구역의 수는 총 4개이다. (빨강 2, 파랑 1, 초록 1) 하지만, 적록색약인 사람은 구역을 3개 볼 수 있다... 이전 1 2 다음
