본문 바로가기

분류 전체보기240

[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.
[BOJ] #2309 일곱 난쟁이 시간 제한 메모리 제한 정답 비율 2 초 128 MB 46.670% 2309번: 일곱 난쟁이 아홉 개의 줄에 걸쳐 난쟁이들의 키가 주어진다. 주어지는 키는 100을 넘지 않는 자연수이며, 아홉 난쟁이의 키는 모두 다르며, 가능한 정답이 여러 가지인 경우에는 아무거나 출력한다. www.acmicpc.net 9명의 난쟁이들 중 진짜 난쟁이는 7명이다. 다행히 7명의 난쟁이들의 키의 합은 100임을 알고 있다. 9명의 난쟁이들이 주어졌을 때 진짜 난쟁이 7명을 찾아 출력하라! 메모리 시간 1998 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 #include #include #include u.. 2019. 9. 19.
[프로그래머스] #42889 실패율 2018년 KAKAO BLIND RECRUITMENT 코딩테스트 연습 - 실패율 | 프로그래머스 실패율 슈퍼 게임 개발자 오렐리는 큰 고민에 빠졌다. 그녀가 만든 프랜즈 오천성이 대성공을 거뒀지만, 요즘 신규 사용자의 수가 급감한 것이다. 원인은 신규 사용자와 기존 사용자 사이에 스테이지 차이가 너무 큰 것이 문제였다. 이 문제를 어떻게 할까 고민 한 그녀는 동적으로 게임 시간을 늘려서 난이도를 조절하기로 했다. 역시 슈퍼 개발자라 대부분의 로직은 쉽게 구현했지만, 실패율을 구하는 부분에서 위기에 빠지고 말았다. 오렐리를 위해 실패율을 구하는 코드를 programmers.co.kr 문제 실패율을 구하는 코드를 완성하라. 실패율은 다음과 같이 정의한다. 스테이지에 도달했으나 아직 클리어하지 못한 플레이어의.. 2019. 9. 9.

티스토리툴바