너와 나의 스토리

문제: www.acmicpc.net/problem/17244 첫 번째 줄에는 집의 가로 길이 N과 세로 길이 M이 입력된다. (3 ≤ N, M ≤ 50) "가로가 N"인 것을 주의하자! 두 번째 줄부터는 집의 구조가 예제 입력과 같이 주어진다. 비어있는 곳은 '.'로 벽은 '#'로 입력된다. 경재 씨의 현재 위치는 S, 나가는 문의 위치는 E, 챙겨야 하는 물건은 종류에 상관없이 X로 입력된다. 챙겨야 하는 물건은 최대 5개까지 있을 수 있다. 집은 언제나 벽으로 둘러싸여 있고, 나가는 문은 언제나 하나이다. 문제 풀이: bfs로 문제를 해결했다. queue에 들어갈 데이터는 다음과 같다. 현재 위치 (x, y) 값 지금까지 습득한 아이템 정보 각 아이템들을 map을 이용해 넘버링해준다. item 번호 ..

문제: www.acmicpc.net/problem/4920 문제 풀이: 위 순으로 각각 2, 2, 4, 4, 1가지 경우의 수가 있다. 각 경우를 vector에 넣어주고, 모든 위치에서 해당 블록들을 놓아 합을 계산했다. 소스 코드: #include #include #include using namespace std; typedef pair P; vector blocks; int n,arr[101][101],caseSize,answer; void init() { vector block; // 1-1 for (int i = 0; i < 4; i++) { block.push_back({ 0,i }); } blocks.push_back(block); block.clear(); //1-2 for (int i =..

문제: programmers.co.kr/learn/courses/30/lessons/17681 입력으로 지도의 한 변 크기 n과 2개의 정수 배열 arr1, arr2가 들어온다. 1 ≦ n ≦ 16 arr1, arr2는 길이 n인 정수 배열로 주어진다. 정수 배열의 각 원소 x를 이진수로 변환했을 때의 길이는 n 이하이다. 즉, 0 ≦ x ≦ 2n - 1을 만족한다. 지도는 한 변의 길이가 n인 정사각형 배열 형태로, 각 칸은 공백(" ") 또는 벽("#") 두 종류로 이루어져 있다. 공백을 그냥 '\0'으로 두면, 틀리므로 주의하자 전체 지도는 두 장의 지도를 겹쳐서 얻을 수 있다. 각각 지도 1과 지도 2라고 하자. 지도 1 또는 지도 2 중 어느 하나라도 벽인 부분은 전체 지도에서도 벽이다. 지도 ..

문제: programmers.co.kr/learn/courses/30/lessons/17680 캐시 크기(cacheSize)와 도시 이름 배열(cities)을 입력받는다. cacheSize는 정수이며, 범위는 0 ≦ cacheSize ≦ 30 이다. cities는 도시 이름으로 이뤄진 문자열 배열로, 최대 도시 수는 100,000개이다. 각 도시 이름은 공백, 숫자, 특수문자 등이 없는 영문자로 구성되며, 대소문자 구분을 하지 않는다. 도시 이름은 최대 20자로 이루어져 있다. 캐시 교체 알고리즘은 LRU(Least Recently Used)를 사용한다. cache hit일 경우 실행시간은 1이다. cache miss일 경우 실행시간은 5이다. 결국 LRU 알고리즘을 구현하는 문제이다. 문제 풀이: do..

문제: programmers.co.kr/learn/courses/30/lessons/17679 입력으로 판의 높이 m, 폭 n과 판의 배치 정보 board가 들어온다. 2 ≦ n, m ≦ 30 board는 길이 n인 문자열 m개의 배열로 주어진다. 블록을 나타내는 문자는 대문자 A에서 Z가 사용된다. 같은 모양의 카카오프렌즈 블록이 2×2 형태로 4개가 붙어있을 경우 사라지면서 점수를 얻는다. 블록이 지워진 후에 위에 있는 블록이 아래로 떨어져 빈 공간을 채우게 된다. 만약 빈 공간을 채운 후에 다시 2×2 형태로 같은 모양의 블록이 모이면 다시 지워지고 떨어지고를 반복하게 된다. 문제 풀이: 먼저 전체 판을 스캔하면서, 2x2가 같은 모양은 블록을 찾고, 이를 blocks 변수에 넣는다. set bl..

문제: programmers.co.kr/learn/courses/30/lessons/17678 셔틀은 항상 09:00에 운행 시작 09:00부터 총 n회 t분 간격으로 역에 도착하며, 하나의 셔틀에는 최대 m명의 승객이 탈 수 있다. 셔틀은 도착했을 때 도착한 순간에 대기열에 선 크루까지 포함해서 대기 순서대로 태우고 바로 출발한다. ex) 09:00에 도착한 셔틀은 자리가 있다면 09:00에 줄을 선 크루도 탈 수 있다. ex) m이 4일 때, 9시 이전에 도착한 사람이 5명이라면, 가장 마지막에 온 사람은 다음 셔틀을 타야 한다. 콘은 같은 시각에 도착한 크루 중 대기열에서 제일 뒤에 선다. 문제 풀이: 먼저, timetable 값들을 정수(분 단위)로 변환시켜 timeV라는 vector에 저장했다...

문제: programmers.co.kr/learn/courses/30/lessons/17677 두 문자열 str1, str2가 입력으로 주어진다. J(A, B) = $\frac{A∩B}{A∪B}$ 대문자와 소문자는 구분하지 않는다. 각 문자열을 두 글자씩 쪼갠다. 이때, 영문자로만 이루어진 글자 쌍만 유효하다. ex) aa1+aa2 단순히 두 글자로 쪼개면 {aa, a1, a+, +a, aa, a2}가 되지만, 유효한 집합은 다음과 같다. => {aa, aa} [ J({str1}, {str2})*65536 ]을 구하라! 문제 풀이: 먼저 각 문자열을 소문자로 통일하였다. 어떤 대문자 C에 대해 char(C-'A'+'a') 연산을 하면, 소문자로 변환할 수 있다. 변환한 문자가 [ 'a'two[1] ||t..

문제: www.acmicpc.net/problem/16955 문제는 "구사과의 돌(x)을 하나 더 뒀을 때, 가로/세로/대각선으로 x가 5개 이상 연속하는지"를 찾는 것이다. 문제 풀이: 모든 점에 대해, 그 점에서 오른쪽의 그림과 같이 4방향으로 5칸을 스캔한다. 5칸 안에 'o'가 존재하지 않고, 'x' 4개가 있다면 바로 1을 리턴해주면 된다. 주의! 처음에는 for(int k=0~5)가 끝나고 cnt('x'의 개수)가 4개이면 바로 1을 리턴해줘 계속 틀렸었다 ㅠㅠ 다음과 같은 경우가 발생할 수 있다. 즉, 현재 'x'를 4개 발견해도 다음에 놓을 곳이 바둑판을 넘어갈 수 있다는 사실을 명심하자! 소스 코드: #include #include #include using namespace std; c..