본문 바로가기

J 바로가기

🔥 PS(Problem Solving) 🔥/BOJ65

[BOJ] #2169 로봇 조종하기 시간 제한 메모리 제한 정답 비율 2 초 512 MB 31.977% 2169번: 로봇 조종하기 첫째 줄에 N, M(1≤N, M≤1,000)이 주어진다. 다음 N개의 줄에는 M개의 수로 배열이 주어진다. 배열의 각 수는 절댓값이 100을 넘지 않는 정수이다. 이 값은 그 지역의 가치를 나타낸다. www.acmicpc.net 방법 로봇이 '아래와 오른쪽'으로 가는 것과 '아래와 왼쪽'으로 가는 것 두 방법을 각각 구해서 더 큰 값으로 dp 배열을 채워나간다. 역시나.. dp는 통찰력!! 통찰력을 키우자ㅜㅜ 메모리 시간 9012 KB 124 ms 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.. 2019. 10. 2.

[BOJ] #1149 RGB 거리 시간 제한 메모리 제한 정답 비율 0.5 초 128 MB 46.756% 1149번: RGB거리 RGB거리에 사는 사람들은 집을 빨강, 초록, 파랑중에 하나로 칠하려고 한다. 또한, 그들은 모든 이웃은 같은 색으로 칠할 수 없다는 규칙도 정했다. 집 i의 이웃은 집 i-1과 집 i+1이고, 첫 집과 마지막 집은 이웃이 아니다. 각 집을 빨강으로 칠할 때 드는 비용, 초록으로 칠할 때 드는 비용, 파랑으로 드는 비용이 주어질 때, 모든 집을 칠하는 비용의 최솟값을 구하는 프로그램을 작성하시오. www.acmicpc.net 문제 N개의 행에 대하여 해당 행(집)을 빨간색, 초록색, 파란색으로 칠할 때 드는 비용이 각각 주어진다. 또한, 그들은 모든 이웃은 같은 색으로 칠할 수 없다는 규칙도 정했다. 집 i의 .. 2019. 10. 2.

[BOJ] #1010 다리놓기 시간 제한 메모리 제한 정답 비율 2 초 128 MB 47.942% 1010번: 다리 놓기 입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트케이스에 대해 강의 서쪽과 동쪽에 있는 사이트의 개수 정수 N, M (0 < N ≤ M < 30)이 주어진다. www.acmicpc.net 방법 'dp[i][j]는 서쪽에 i 개의 점이 있고, 동쪽에 j 개의 점이 있다고 했을 때 놓을 수 있는 다리의 수' 라고 정의를 해보았다.그리고 그림을 그려봤는데, 같은 i개의 점일 때는 j값에 따라 같은 모습의 다리들이 반복되는 것을 볼 수 있었고 왼쪽 상단에 보이듯이 표를 채워보니 아래와 같은 규칙을 찾아낼 수 있었다. 그래서 식을 세워보면 이렇게 된다. i == 1 dp[i][j] = j.. 2019. 10. 2.

[BOJ] #14891 톱니바퀴 시간 제한 메모리 제한 정답 비율 2 초 512 MB 49.598% 14891번: 톱니바퀴 총 8개의 톱니를 가지고 있는 톱니바퀴 4개가 아래 그림과 같이 일렬로 놓여져 있다. 또, 톱니는 N극 또는 S극 중 하나를 나타내고 있다. 톱니바퀴에는 번호가 매겨져 있는데, 가장 왼쪽 톱니바퀴가 1번, 그 오른쪽은 2번, 그 오른쪽은 3번, 가장 오른쪽 톱니바퀴는 4번이다. 이때, 톱니바퀴를 총 K번 회전시키려고 한다. 톱니바퀴의 회전은 한 칸을 기준으로 한다. 회전은 시계 방향과 반시계 방향이 있고, 아래 그림과 같이 회전한다. 톱니바퀴를 회전시키려 www.acmicpc.net 방법 톱니바퀴들을 gears 라는 배열에 저장해 두고 회전시킬 톱니바퀴를 gear 라고 했을 때, gear 기준으로 왼쪽 톱니바퀴들과.. 2019. 10. 2.

[BOJ] #14889 스타트와 링크 시간 제한 메모리 제한 정답 비율 2 초 512 MB 50.576% 14889번: 스타트와 링크 예제 2의 경우에 (1, 3, 6), (2, 4, 5)로 팀을 나누면 되고, 예제 3의 경우에는 (1, 2, 4, 5), (3, 6, 7, 8)로 팀을 나누면 된다. www.acmicpc.net 방법 1 : vector 이용 Brute Force 로 스타트팀의 구성원을 구해고, 스타트팀의 구성원을 기반으로 링크팀의 구성원을 알아낸다. 그렇게 팀의 구성원을 알아낸 후에 각 팀의 능력치를 계산하여 비교하고 MIN 값을 매번 갱신시킨다. 함수 설명 인자 idx는 인덱스 순서를 나타내고, cnt 는 스타트팀의 구성원이 아닌 사람의 숫자이다. 스타트팀과 링크팀의 구성원은 무조건 n/2 명이므로 스타트팀의 구성원이 아닌.. 2019. 10. 2.

[BOJ] #3190 뱀 시간 제한 메모리 제한 정답 비율 1 초 128 MB 31.052% 3190번: 뱀 문제 'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다. 게임은 NxN 정사각 보드위에서 진행되고, 몇몇 칸에는 사과가 놓여져 있다. 보드의 상하좌우 끝에 벽이 있다. 게임이 시작할때 뱀은 맨위 맨좌측에 위치하고 뱀의 길이는 1 이다. 뱀은 처음에 오른쪽을 향한다. 뱀은 매 초마다 이동을 하는데 다음과 같은 규칙을 따 www.acmicpc.net 테스트케이스 testcase 1 20 13 6 15 7 18 20 14 14 13 11 9 7 10 3 18 10 10 13 13 13 5 6.. 2019. 9. 29.

[BOJ] #16929 Two Dots 시간 제한 메모리 제한 정답 비율 2 초 512 MB 50.417% 16929번: Two Dots 첫째 줄에 게임판의 크기 N, M이 주어진다. 둘째 줄부터 N개의 줄에 게임판의 상태가 주어진다. 게임판은 모두 점으로 가득차 있고, 게임판의 상태는 점의 색을 의미한다. 점의 색은 알파벳 대문자 한 글자이다. www.acmicpc.net 실버 3 이라서 조금 겁을 먹었는데 술술풀려서 놀랐던 문제다. 기존 그래프의 사이클 문제와는 다르게 변을 공유해야하는 조건이 추가되어 생각을 해보니, 이전에 왔던 방향으로 다시 탐색을 못하게끔 구현을 하면 되겠다 싶어 구현해보니 의외로 매개변수 하나만 추가하고 반복문에 조건 하나만 넣으면 되어 쉽게 풀 수 있었다. 그리고 항상 nr, nc 변수를 지역변수로 선언하다가 전역.. 2019. 9. 29.

[BOJ] #6359 만취한 상범 시간 제한 메모리 제한 정답 비율 1 초 128 MB 69.799 % 6359번: 만취한 상범 문제 서강대학교 곤자가 기숙사의 지하에는 n개의 방이 일렬로 늘어선 감옥이 있다. 각 방에는 벌점을 많이 받은 학생이 구금되어있다. 그러던 어느 날, 감옥 간수인 상범이는 지루한 나머지 정신나간 게임을 하기로 결정했다. 게임의 첫 번째 라운드에서 상범이는 위스키를 한 잔 들이키고, 달려가며 감옥을 한 개씩 모두 연다. 그 다음 라운드에서는 2, 4, 6, ... 번 방을 다시 잠그고, 세 번째 라운드에서는 3, 6, 9, ... 번 방이 열려있으면 잠그고 www.acmicpc.net 문제 n개의 방이 일렬로 늘어선 감옥이 있다. 각 방에는 벌점을 많이 받은 학생이 구금되어있다. 첫 번째 라운드에서 상범이는 모든.. 2019. 9. 19.

[BOJ] #14501 퇴사 시간 제한 메모리 제한 정답 비율 2 초 512 MB 46.680% 14501번: 퇴사 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. www.acmicpc.net 주어진 N일 동안에 백준이가 최대의 이익을 볼 수 있도록 일을 선택해야 한다. 틀렸던 이유 시작하는 날짜를 st, 끝나는 날짜를 end 보수를 p 라고 봤을 때 end 값을 기준으로 오름차순 정렬을 하여 p를 더했다가 틀려버렸다.. 분명 2년 전 스터디하면서 풀었을 때는 누군가가 이렇게 풀었었는데 예외처리가 떠오르지 않아 dp로 고쳐서 다시 풀었다. 메모리 시간 1988 KB 0 ms 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 .. 2019. 9. 19.

이전 1 ··· 3 4 5 6 7 8 다음

티스토리툴바