접근 제한자: public, private

class NewClass
    def initialize(name)    
        @name = name
    end

    public
    def public_method
        puts "public"
    end

    private
    def private_method
        @private_value = 1
    end
end

값 읽기: attr_reader

class NewClass
    def initialize(name)
        @name = name
     end

     def name
         @name
     end
end

위 코드의 name 메소드를 attr_reader를 이용해 한 줄로 작성 가능

리팩토링

class NewClass
    attr_reader :name

    def initialize(name)
        @name = name
     end
end

값 접근: attr_writer

attr_reader와 마찬가지로, 값 수정 역시 한 줄로 가능하다.

class NewClass
    def name=(value)
        @name = value
    end

    # 한 줄로 리팩토링
    attr_writer :name
end

읽기 및 접근 모두 가능: attr_accessor

class NewClass
    attr_accessor :name

    # initialize 메소드
end

모듈: module

모듈: 클래스에서 사용할 기능들(메소드)을 제공하기 위해 만듦. 다양한 클래스에서 사용가능한 메소드를 제공하는 라이브러리.

모듈 예시: Math

puts Math::PI

루비에는 Math::PI와 Circle::PI가 있으므로, 혼동하지 않기 위해 네임스페이스를 지정해준다(Math::

모듈 사용: require

require 'date'

클래스에 모듈을 포함: include

class Angle
    include Math

    def initialize(radians)
    @radians = radians
  end

  def cosine
    cos(@radians)
  end
end

이렇게 작성할 경우, Math::라고 네임스페이스를 작성하지 않고 모듈의 메소드?를 사용 가능.

클래스의 기본 구조

class NewClass
    # Class 내부 코드 작성
end

클래스 내부에는 당연하게도 (생성자를 포함한) 함수 선언이 가능하다. 인스턴스 변수의 선언에는 @을 사용한다.

생성자 선언

class NewClass
    def initialize(param)
        @param = param
    end
end

# 생성자로 객체 생성
class = newClass.new("param1")

변수: @, @@, $

인스턴스 변수: @ 클래스 변수: @@ 전역 변수: $

class NewClass
    $global_value = "global"
    @@class_value = "class"

    def initialize(instance_value)
        @instance_value = instance_value
    end
end

puts $global_value

클래스 상속: <

class InheritClass < NewClass
end

함수 오버라이딩은 함수명을 그대로 써서 재정의?하면 된다.

class NewClass
    def method1
        return "Hello"
     end

     def method2(param)
         return "Hello #{param}"
 end

 class InheritClass < NewClass
     # 오버라이딩 1
     def method1
        return "Hi"
    end

    # 오버라이딩 2
    def method2(param)
        super(param)
    end
end

클래스 메소드: 클래스명.메소드명

class NewClass
    def NewClass.method
    end
end

collect와 map은 같은 기능

my_nums = [1, 2, 3]
my_nums.collect {|x| x ** 2}
# ==> [1, 4, 9]를 반환, but 원본 배열(my_nums)은 변경되지 않음

new_nums = my_nums.collect {|x| x ** 2}
# new_nums = [1, 4, 9]
# my_nums = [1, 2, 3]

my_nums.collect! {|x| x ** 2|
# !를 붙이면 원래 배열을 변형

메소드의 제어권을 전달: yield

def block_test
    puts "a"
    puts "b"
    yield
    puts "c"
end

block_test {puts "d"}
# a -> b -> d -> c

yield를 통해 파라미터를 전달하는 것도 가능!

def yield_test(name)
    puts "Hello"
    yield(name)
    puts "Bye"
    yield("Rou")
end

yield_test("Sho") {|n| puts "My name is #{n}"}

# Hello
# My name is Sho
# Bye
# My name is Rou

프로세스: proc

Proc: 코드 블록을 객체로 만들어서 변수에 저장하거나 전달할 수 있도록 하는 기능 => Ruby의 객체지향!

프로세스 정의: .new

floasts = [1.2, 3.45, 5.6, 2.7]

round_down = Proc.new { |x| x.floor }

ints = floats.collect(&round_down)

프로세스 호출: .call

hi = Proc.new {puts "Hello!"}
hi.call
# Hello!

메소드를 전달: &:method_name

string = ["1", "2", "3"]
int = string.map(&:to_i)
# int = [1, 2, 3]

람다: lambda

lambda: 코드 블록을 객체로 만들어서 변수에 저장하거나 전달할 수 있도록 하는 기능 => Ruby의 객체지향!

람다 정의: lambda

my_lambda = lambda { |param| block }

my_array = ["string1", :symbol1, "string2", :symbol2]

symbol_filter = lambda {|param| param.is_a? Symbol}

symbols = my_array.select(&symbol_filter)
# symbols = [:symbol1, :symbol2]

proc과 lambda의 차이

1. 인수 처리 방식

   • lambda : 인수 검사를 엄격히 함. 인수 수가 맞지 않으면 ArgumentError 발생
   • proc : 누락된 인수는 nil로 처리

2. return 동작 방식

   • lambda : lambda의 return은 호출된 위치로 돌아가 다음 코드를 실행
   • proc : proc의 return은 정의된 메소드 전체를 즉시 종료시킴

def test_lambda
    my_lambda = lambda { return "Lambda finished"}
    result = my_lambda.call
    "Result after lambda: #{result}"  # 이 줄까지 모두 실행
end

puts test_lambda
# Result after lambda: Lambda finished


def test_proc
    my_proc = Proc.new { return "Proc finished"}
    result = my_proc.call  # test_proc 메소드 즉시 종료
    "Result after proc: #{result}"  # 이 줄은 실행되지 않음
end

puts test_proc
# Proc finished

# 기존 if 문 작정
if condition
    # Do Something
end

# if 문을 더 간단하게 리팩토링
expression if boolean

# 기존 unless 문 작성
unless condition
    # Do Something
end

# if 문을 더 간단하게 리팩토링
expression unless boolean

# 삼항연산자
puts 3 < 4 ? "true" : "false"
# true 출력

case 문을 간결하게

# 기존 case 문 작성
case language
    when "JS"
        puts "websites!"
    when "python"
        puts "ai"
    else    
          puts "I don't know!"
end

# case 문을 더 간단하게 리팩토링
case language
    when "JS" then puts "websites!"
    when "python" then puts "ai"
       else puts "I don't know!"
end

대입 연산자(conditional assignment): ||=

값이 없는 경우(nil인 경우) 대입, 그렇지 않은 경우는 유지

object = nil
object ||= "name"
puts object
# Output: name

object ||= "age"
puts object
# Output: name

object = "age"
puts object
# Output: age

함수 리팩토링: return 제거

def add(x, y)
    return x + y
end

# 리팩토링: return 제거
def add(x, y)
    x + y
end

범위: .upto, .downto

.upto(num)은 num까지 +1 되는거 예를 들어, 95.upto(100)이면, 95, 96, 97, 98, 99, 100이 해당

.downto(num)은 num까지 -1 되는거

숫자뿐만 아니라 문자의 오름차순, 내림차순도 가능하다.

"L".upto("P") {|c| print c}
# LMNOP

특정 메소드를 응답할 수 있는지 확인: respond_to?(:method명)

age = 140

age.respond_to?(:next)
# true

추가: push, +=, <<

array = [1, 2, 3]
array.push(4)
array << 5

string = "My name "
string += "is "
string << "Ruby!"

switch와 비슷

case choice
when "add"
  puts "Added!"
when "update"
  puts "Updated!"
when "display"
  puts "Movies!"
when "delete"
  puts "Deleted!"
else
  puts "Error!"
end

입력받을 때 값을 지정할 수 있음

title = gets.chomp.to_sym # 입력받은 값을 symbol 타입으로 지정
rating = gets.chomp.to_i # 입력받은 값을 정수형으로 지정

해시에 값이 존재하는지 확인: .nil?

heroes = {
    Dytica: 4,
    Oriens: 4,
    Krisis: 3
}

if heroes["TUA".to_sym].nil?
    puts "ERROR"
end
# heroes 해시에 TUA라는 심볼을 key로 갖는 값이 없으므로 ERROR 출력

해시에서 값 삭제: .delete(key)

heroes.delete(key)

:으로 시작하는 문자열, immutable(변경 불가능) 메모리에 한 번만 저장됨

# string과 symbol 비교
puts "string".object_id
puts "string".object_id
# 두 개의 object_id의 값은 다름

puts :symbol.object_id
puts :symbol.obkect_id
# 두 개의 object_id의 값은 같음

# symbol 생성
my_symbol = :symbol

symbol_hash = {
    :one => 1,
    :two => 2,
    :three => 3
}

string을 symbol로 변환: to_sym, intern

strings = ["a", "b", "c"]

symbols = []
strings.each do |s|
    symbols.push s.to_sym
    # symbols.push s.intern 도 동일하게 작동!
end

조건에 맞는 값만 필터링: .select

grades = {
    sho: 100,
    rou: 80,
    rai: 70,
    getsu: 50
}

good = grades.select { |name, grade| grade > 60}

.each_key, .each_value

grades = {
    sho: 100,
    rou: 80,
    rai: 70,
    getsu: 50
}

grades.each_key {|key| puts key}
# sho \n rou \n ...

grades.each_value {|value| puts value}
# 100 \n 80 \n ...

hash의 모양?

hash rocket 타입

hash_rocket = {
    "one" => 1,
    "two" => 2
}

Ruby 1.9. 버전부터 바뀐 syntax : 더 간단해짐

new_hash = {
    one: 1,
    two: 2,
    three: 3
}

def를 이용하여 메소드를 정의함

def print_text
    print "Print Method!"
end

print_text
#Print Method!

파라미터가 있는 메소드

def friend(name)
    puts "Hello #{name}"
end

def friends(greeting, *friends)
    friends.each {|friend| puts "#{greeting}, #{friend}!"}
end

# greeting에 해당하는 파라미터("Hello") 이외의 파라미터는
# 모두 freinds 배열의 파라미터로 전달
friends("Hello", "Rube", "Rou", "Rai")

# 파라미터에 default 값 지정
def alphabetize(arr, rev = false)

end

반환값이 있는 메소드

def add(x, y)
    return x + y
end

puts add(1, 2)

결합 비교 연산자(Combined Comparision Operator): <=>

<=>: 두 개의 Ruby 객체를 비교하는 연산자

a <=> b의 경우, 첫번재 피연산자(이하 a)와 두번째 피연산자(이하 b)가 같은 경우: 0 a가 b보다 큰 경우: 1 a가 b보다 작은 경우: -1

<=>를 이용하여 정렬

num = [2, 3, 1, 5, 4]

# 오름차순 정렬
num.sort! do |x, y|
    x <=> y
end

# 내림차순 정렬
num.reverse!

my_array = [1, 2, 3]

# index로 접근
print my_array[0]

string_array = ["a", "b", "c"]
array_array = [[0, 0, 0, 0], [1, 1, 1, 1], [2, 2, 2, 2]]

# array_array 출력
array_array.each { |x| puts "#{x}"}
# [0, 0, 0, 0]
# [1, 1, 1, 1]
# [2, 2, 2, 2]

# 2차원 배열의 각 원소에 접근
array_array.each {|element|
    element.each {
        |x| puts x
    }
}
# {} 대신 do, end로 작성해도 됨

hash

# 빈 hash 생성
hash = Hash.new

# defalut 값 지정
hash = Hash.new(0)
hash = Hash.new("default value")

# 처음부터 값이 있는 hash 생성
hash = {
    key1 => value1,
    key2 => value2,
    key3 => value3
}

# hash에 key-value pair 추가
hash["key4"] = "value4"

hash.each {|x| puts x}
# [key1, value1]
# [key2, value2]

hash.each {|x, y| puts "#{x}: #{y}"}
# key1: value1
# key2: value2

정렬: sort, sort_by

array 정렬: sort hash 정렬: sort_by

colors = {
    "red" => 3,
    "blue" => 2,
    "pruple" => 1
}

# 오름차순
colors = colors.sort_by do |key, value| value end
# 내림차순
colors.reverse!

문자열로 변환: to_s

num = 3
puts num.to_s

array로 변환: to_a

array = (1..10).to_a

while

주어진 조건이 성립하는 동안(true) while 문 내부 동작 수행

counter = 0

while counter < 10
    puts counter
    counter = counter + 1
end

# 0 ~ 9 출력

until

주어진 조건이 성립할 때까지(false) until 문 내부 동작 수행

 counter = 0

 until counter == 10
     puts counter 
    counter = counter + 1
 end
 # 0 ~ 9 출력

for

주어진 범위나 배열을 사용하여 반복적인 동작 수행

 # ... : 마지막 수를 범위에 포함하지 않음 [1, 10)
 for num in 1 ... 10
     puts num
 end
 # 1 ~ 9 출력

 # .. : 마지막 수를 범위에 포함 [1, 10]
 for num in 1 .. 10
     puts num
 end

loop

while true와 같은 무한 루프, break문을 통해 탈출 가능

 num = 0

 loop do
     num -= 1
    puts num
    break if num <= 0
 end

next

특정 조건이 성립하면 스킵 (continue)

 for i in 1 .. 5
     next if i % 2 == 0
    puts i
 end

배열: .each

my_array = [1, 2, 3, 4, 5]

배열의 값을 이용하여 반복문 실행

 numbers = [1, 2, 3, 4, 5]

 numbers.each{|item| print item}

 numbers.each do |item|
     puts item
 end

.times

super compact for 반복문이라고 한다. 10.times이면 10번 반복

 10.times {puts "abc"}

문자열 분리: .split

 text = "Hello, Ruby!"
 words = text.split(" ")
 # words = ["Hello", "Ruby!"]

if

boolean 값: true, false

if 1 < 2
    print "1 is less than 2"
end

else

user_num = Integer(gets.chomp)

if user_num < 100
    print "#{user_num} is less than 100"
else
    print "#{user_num} is bigger than 100"
end

elsif

elsif는 또 처음 본다

user_num = Integer(gets.chomp)

if user_num < 100
    print "#{user_num} is less than 100"
elsif user_num > 100
    print "#{user_num} is bigger than 100"
else
    print "#{user_num] is 100"
end

unless

if not(false 체크)을 의미하는 조건문이다 좀 헷갈리긴 한데 if의 경우 if (true == true) unless의 경우 unless (false == false) 라고 생각하면 될 것 같다

hungry = false

unless hungry 
    print "I'm not hungry"
else
    print "It's time to eat"
end

true, false

is_true = 2 != 3
is_false = 2 == 3

연산자

비교 연산자

<, <=, >, >=

논리 연산자

&&, ||, !

메소드

입력: gets.chomp 특정 문자열을 포함하는지 확인: string_to_check.include? "substring" 문자열 일부 교체: string_to_change.gsub!(/s/, "th")

다시 한 번 출력 메소드의 차이를 정리하자면

puts: 주어진 문자열 출력 및 개행 print: 주어진 문자열 출력

puts "Hello Ruby!"
puts "Hello" + "Ruby!"

name = Ooing
puts "Hello #{name}!"
# Output: Hello Ooing!

입력: gets.chomp

gets: 엔터 입력 전까지의 내용을 input으로 받음, 자동적으로 빈 줄(blank line)을 추가 chomp: 추가 라인(blank line)을 제거하는 역할

print "What's your name?"
name = gets.chomp

# Oupput: What's your name? (값 입력 + enter)
# name에 입력된 값 저장

첫 문자를 대문자로: .capitalize

새로운 변수에 값을 할당하는 경우: new_value = value.capitalize 기존 값을 변경하는 경우: value.capitalize!

```ruby name = "ruby"

name2에 name의 첫 문자를 대문자로 변환한 문자열을 할당

name2 = name.capitalize

name에 그대로 첫 문자를 대문자를 변환하여 할당

name.capitalize!

puts "My name is #{name}." puts "My name is #{name2}."

Output: My name is Ruby.

Ruby

Ruby는 웹/인터넷 개발, 텍스트 처리, 게임 개발 및 웹 개발 프레임워크인 Ruby on Rails로 사용할 수 있는 유연한 프로그래밍 언어.

특징

1. 고급 프로그래밍 언어(High-Level) : 사람이 이해하기 쉽게 작성된 언어 = 영어랑 비슷
2. 인터프리트 언어 : 코드 작성 및 실행에 컴파일러 필요 X
3. 객체 지향 : 사용자가 데이터 구조(객체)를 조작하여 프로그램을 빌드 및 실행 가능, 루비의 모든 것이 객체
4. 사용하기 쉬움 : 컴퓨터의 필요보다 인간의 필요를 강조

변수 타입: int, string, boolean 등

객체 지향 언어이기 때문에, 모든 데이터 타입은 클래스 기반.

변수 선언 시 타입 선언 필요 X

# Integer type
count = 1

# Float type
rating = 1.5

# Boolean type
isBig = count > 2

# Print
puts isBig
# Output : false


# Both float and integer types
miles = 127
hours = 2.5
miles_per_hour = miles/hours

# Print
puts "Miles per hour : #{miles_per_hour}"
# Output : Miles per hour: 50.8


# String type
name = "Ruby"

puts name
# Output : Ruby

연산자

+(덧셈), -(뺄셈), *(곱셈), /(나눗셈), **(거듭제곱), %(모듈로)

연산자는 대부분 프로그래밍 언어와 같고, \(거듭제곱)을 지원**

기본 메소드

기본적으로 메소드는 .을 사용하여 호출.

출력: puts, print

puts: 주어진 문자열 출력 및 개행 print: 주어진 문자열 출력

puts "Hello"
puts "Ruby"
# Output:
# Hello
# Ruby

print "Hello"
print "Ruby"
# Output:
# HelloRuby

크기: .length

puts "Hello Ruby".length
# Output: 10

거꾸로 뒤집기: .reverse

puts "Ruby".reverse
# Output: ybuR

대소문자 변환: .upcase, .downcase

# 모두 대문자로
puts "Ruby".upcase
# Output: RUBY

# 모두 소문자로
puts "Ruby".downcase
# Output: ruby

주석

한 줄 주석

#으로 한 줄 주석 작성 가능

# 지금까지 계속 쓰고 있던
# 한 줄 주석

여러 줄 주석

=begin ~~ =end으로 여러 줄 주석 작성 가능

=begin
여러 줄 주석을
작성하는 방법
=end

Addressable Asset System

이 글을 (만약) 보는 사람들이 있다면 이런 내용은 다 알겠지.. 그러므로 간단히 작성한다.

Addressable Asset System을 이용하면 실행 시간에 필요한 리소스들을 프로그램(앱) 내부에 저장하고있지 않아도 사용 가능하다. 로컬 또는 원격에서 다운로드할 수 있기 때문!

이로 인해 Addressable을 사용하는 데에는 이점이 꽤나 많은데..

1. 프로그램의 크기를 줄일 수 있다 (본인은 Addressable을 도입하여 약 1/10으로 앱의 크기를 줄였다!)
2. 리소스 다운로드를 위해 앱을 재설치할 필요가 없다 (런타임에서 다운로드 가능하므로)

무엇을 Addressable Asset으로 만들까?

prefab, image뿐만 아니라 scene, animation, animator.. 거의 모든 것들을 Addressable로 지정할 수 있다. (스크립트는 안 됨)

그래서 상황에 맞게, 본인의 필요에 맞게 어떤 것을 addressable asset으로 만들지 결정해야한다.

첫번째 프로젝트에서는 prefab을, 두번째 프로젝트에서는 scene을 addressable화 했다.

prefab을 addressable asset으로 만들면 프로젝트의 용량을 확실히 줄일 수 있다. (2500개 이상이었기 때문에) 또한, prefab을 리소스에 포함해서 빌드하면 수정할 때마다 새로 빌드 & 출시해야하는데, addressable로 관리하면 프리팹 수정으로 새로 빌드할 필요가 없어진다!

scene을 addressable asset으로 만드는 것 역시, 용량면에서 매우 훌륭하다.(씬에 포함되는 모든 것들을 프로젝트에서 제외하고 빌드할 수 있으므로) scene을 addressable asset으로 만들면 scene의 다운로드 속도가 느린 것 아닌가? 라고 생각할 수 있는데(일단 본인이 이렇게 생각했었다) 전혀 아니다! 위의 prefab 하나만 addressable해서 다운로드하는 것과 거의 차이가 없다.(유니티 Addressable 공식 문서에도 SceneManager.LoadScene과 Addressables.LoadScene()의 성능 차이가 거의 없다고 적혀있다)

Addressable? Group? Label?

첫번째 프로젝트에서는 하나의 group에 하나의 asset만 배치했다.

이렇게 하면 group 생성하는게 번거롭긴 해도, 선택한 1개만 다운로드하기에는 효율적이다. (여러 asset을 group으로 묶으면 하나를 다운로드받기 위해 같은 group에 속한 모든 asset을 다운로드하기 때문에) 그룹 생성하는건 왜 번거로웠냐면.. 무려 에셋과 번들이 2500개 이상이었기 때문이다.

두 번째 프로젝트에서는 하나의 group에 여러개의 asset을 배치했다.

하나의 group에 속한 asset들을 모두 동시에 다운로드하기 위해! 이 경우의 이점은 뭐냐면, 같은 그룹에 속한 asset을 모두 한 번에 다운로드할 수 있어서 초기에 모두 로딩하고 이후에 사용 시점에 불러오는 시간이 들지 않는다!

예를 들면, 게임을 실행할 때 앱스토어에서 업데이트하지 않고 패치 파일을 다운로드하는 것과 비슷하다.

Addressable 다운로드 스크립트

프로그레스 바

이런 식으로 Addressable bundle의 다운로드 상황에 맞게 프로그레스 바가 보였으면 좋겠다고 생각했다. (다음 담당자가 서치하다가 이 글을 볼 일은.. 없겠지..?🥹)

메인 프로젝트와 Addressable 프로젝트 분리

난 주로 메인 프로젝트와 Addressable 프로젝트를 분리해서 작업을 했다.

분리헸더니갑자기 InvalidKeyException이 발생하는 경우가 있는데, 대부분 Addressable Build를 하지 않아서이다. Load Path를 변경한 뒤, build를 해야 제대로 적용이 된다.

InvalidKeyException 이 발생하는 경우

1. Key 값이 잘못 됨

    Addressables.InstantiateAsync("KEY", new Vector3(0, 0, 0), Quaternion.identity);

2. Remote Load Path가 잘못 됨
3. Bundle Build 시의 Remote Load Path와 현재 설정된 Remote Load Path가 다름
4. 모든게 제대로 설정돼있음에도 오류가 발생하는 경우, Cache 삭제! (C:/Users/user/AppData/LocalLow/회사 이름/앱 이름)

어차피 혼자 작업하면서 왜? 라는 생각이 들 수 있지만.. 프로젝트 사이즈가 너무 커서 한 프로젝트에서 관리하면 감당이 안 됐다..😱 프로젝트 여는데만 10분.. 20분...

프리팹을 Addressable 에셋으로 변환하는데는 별 문제 없었다. 애니메이션도 잘 적용되고, 레이어 순서가 깨지지도 않고 등등. Addressable을 잘 몰라서 헤맨 것 제외하고는 잘 됐다. (뭘 헤맸는지도 후술 예정)

씬을 Addressable 에셋으로 변환하는데는 생각보다 다양한 문제가 뒤따랐다.

• 버튼 OnClick 동작 안 함
• 스크립트 변환 적용 안 됨
• 레이어 순서 깨짐 <- 😫

Addressable을 더 잘 이용하고 싶다.

이게 무슨 말이냐면, 콘텐츠의 업데이트만 있을 경우 앱을 새로 빌드하고 싶지 않다는 뜻이다. Addressable 에셋을 다운로드받기만 하면 업데이트가 적용되는.

이걸 적용하기 위해선 스크립트를 변경할 필요가 있었다. 기존 코드는 매~우 하드코딩이었기 때문.

오늘의 문제 2295 세 수의 합 1654 랜선 자르기 18869 멀티버스 Ⅱ

2295 세 수의 합

코드

#include <bits/stdc++.h>
using namespace std;

int n;
vector<int> arr, two;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n;
    arr = vector<int>(n, 0);
    for (int i = 0; i < n; i++) cin >> arr[i];
    sort(arr.begin(), arr.end());
    arr.erase(unique(arr.begin(), arr.end()), arr.end());

    for (int i = 0; i < arr.size(); i++) {
        for (int j = i; j < arr.size(); j++) {
            two.emplace_back(arr[i] + arr[j]);
        }
    }
    sort(two.begin(), two.end());
    two.erase(unique(two.begin(), two.end()), two.end());

    for (int i = arr.size() - 1; i >= 0; i--) {
        for (int j = arr.size() - 2; j >= 0; j--) {
            if (binary_search(two.begin(), two.end(), arr[i] - arr[j])) {
                cout << arr[i];
                return 0;
            }
        }
    }
}

1654 랜선 자르기

코드

#include <bits/stdc++.h>
using namespace std;

long long k, n, arr[10002];

int count(int len) {
    long long cnt = 0;
    for (int i = 0; i < k; i++) {
        cnt += arr[i] / len;
    }
    return cnt;
}

int main() {
    cin >> k >> n;
    for (int i = 0; i < k; i++) cin >> arr[i];
    sort(arr, arr + k);
    long long s = 1, e = arr[k - 1];
    while (s < e) {
        long long mid = (s + e + 1) / 2;
        if (count(mid) >= n) s = mid;
        else e = mid - 1;
    }
    cout << s;
}

이런 문제를 Parametric Search라고 한다고 한다.

18869 멀티버스 Ⅱ

코드

#include <bits/stdc++.h>
using namespace std;

int m, n;
vector < vector<int>> arr;


int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> m >> n;
    for (int i = 0; i < m; i++) {
        vector<int> v;
        for (int j = 0; j < n; j++) {
            int a;
            cin >> a;
            v.emplace_back(a);
        }
        arr.emplace_back(v);
        sort(v.begin(),v .end());
        for (int j = 0; j < n; j++) {
            arr[i][j] = lower_bound(v.begin(), v.end(), arr[i][j]) - v.begin();
        }
    }
    int ans = 0;
    for (int i = 0; i < m - 1; i++) {
        for (int j = i + 1; j < m; j++) {
            bool same = true;
            for (int k = 0; k < n; k++) {
                if (arr[i][k] != arr[j][k]) {
                    same = false;
                    break;
                }
            }
            if (same) ++ans;
        }
    }
    cout << ans;
}

처음에는 그냥 인덱스 저장 후 정렬해서 순서대로 인덱스가 같은지 확인했는데, 이렇게 할 경우 10 10 / 20 10 을 같다고 처리한다! 그렇기 때문에 단순 정렬이 아닌 좌표 압축을 해서 lower_bound를 비교해야 한다.

오늘의 문제 6064 카잉 달력 11051 이항 계수 2

6064 카잉 달력

코드

#include <bits/stdc++.h>
using namespace std;

int t, m, n, x, y;

int last(int a, int b) {
    int tmp, ta, tb;
    if (a > b) {
        ta = a; tb = b;
    }
    else {
        ta = b; tb = a;
    }
    while (ta != 0) {
        tmp = tb % ta;
        tb = ta;
        ta = tmp;
    }
    return (a * b) / tb;
}

int main() {
    cin >> t;
    while (t--) {
        cin >> m >> n >> x >> y;
        int mn = last(m, n);
        if (m == x && n == y) {
            cout << mn << "\n";
            continue;
        }
        int ans = -1;
        for (int i = x; i <= mn; i += m) {
            if (i % n == y || (n == y && i % n == 0)) {
                ans = i;
                break;
            }
        }
        cout << ans << "\n";
    }
}

11051 이항 계수 2

코드

#include <bits/stdc++.h>
using namespace std;
#define ll long long

int n, k, dp[1002][1002];

int main() {
    cin >> n >> k;
    dp[1][0] = 1;
    dp[1][1] = 1;
    for (int i = 2; i <= n; i++) {
        for (int j = 0; j <= i; j++) {
            dp[i][j] = (dp[i - 1][j] + dp[i - 1][j - 1]) % 10007;
        }
    }
    cout << dp[n][k];
}

문득.. nCk = n-1Ck + n-1Ck-1 이라는 공식이 떠올랐다..

오늘의 문제 1005 ACM Craft 1029 그림 교환

1005 ACM Craft

코드

#include <bits/stdc++.h>
using namespace std;

int t, n, k, w;
int arr[1002], dp[1002];
vector<vector<int>> adj;

int dfs(int d) {
    ios::sync_with_stdio(0);
    cin.tie(0);
    if (dp[d] != -1) return dp[d];
    if (adj[d].empty()) {
        dp[d] = arr[d];
        return dp[d];
    }
    int now = 0;
    for (int i : adj[d]) {
        now = max(now, dfs(i));
    }
    dp[d] = arr[d] + now;
    return dp[d];
}

int main() {
    cin >> t;
    while (t--) {
        cin >> n >> k;
        adj = vector<vector<int>>(n, vector<int>(0, 0));
        fill(dp, dp + n, -1);
        for (int i = 0; i < n; i++) cin >> arr[i];
        while (k--) {
            int a, b;
            cin >> a >> b;
            adj[b - 1].emplace_back(a - 1);
        }
        cin >> w;
        cout << dfs(w - 1) << "\n";
    }
}

그래프를 역방향으로 만들었다.

1029 그림 교환

코드

시간 초과

#include <bits/stdc++.h>
using namespace std;

int n, arr[16][16], max_num;
int vis[16];

void dfs(int k, int p, int num) {
    if (k == n) {
        max_num = max(num, max_num);
        return;
    }
    vis[k] = 1;
    for (int i = 0; i < n; i++) {
        if (!vis[i] && arr[k][i] >= p) {
            dfs(i, arr[k][i], num + 1);
            vis[i] = 0;
        }
    }
    max_num = max(max_num, num);
}

int main() {
    cin >> n;
    for (int i = 0; i < n; i++) {
        string s;
        cin >> s;
        for (int j = 0; j < n; j++) {
            arr[i][j] = s[j] - '0';
        }
    }
    dfs(0, 0, 1);
    cout << max_num;
}

처음에 dfs만 이용해서 풀었는데, 시간 초과가 발생했다. 당연히 중복 연산이 많았겠지.. 라고 생각하며 해당 코드에 dp를 적용하려고 했는데..??

도무지 모르겠어서 구글링으로 참고했다!! 그랬더니 방문한 사람을 비트 마스크를 이용해서 푸는 방법을 이용하더라. 방문을 표시할 필요가 있고, 사람 수가 적은 경우는 비트 마스크를 사용할 수 있다는 것을 배웠다.

비트 마스크 이용 및 성공

#include <bits/stdc++.h>
using namespace std;

int n, arr[16][16], dp[16][10][1 << 16];

int dfs(int k, int p, int vis) {
    int& ret = dp[k][p][vis];
    if (ret != -1) return ret;
    ret = 0;
    for (int i = 0; i < n; i++) {
        if (!(vis & (1 << i)) && arr[k][i] >= p) {
            int nv = vis | (1 << i);
            ret = max(ret, dfs(i, arr[k][i], nv) + 1);
        }
    }
    return ret;
}

int main() {
    cin >> n;
    for (int i = 0; i < n; i++) {
        string s;
        cin >> s;
        for (int j = 0; j < n; j++) {
            arr[i][j] = s[j] - '0';
        }
    }
    memset(dp, -1, sizeof(dp));
    dfs(0, 0, 1);

    cout << dp[0][0][1] + 1;
}

비트 마스크 이용하는 문제들을 더 풀어봐야겠다.

오늘의 문제 두 큐 합 같게 만들기 시소 짝꿍

두 큐 합 같게 만들기

문제 설명 길이가 같은 두 개의 큐가 주어집니다. 하나의 큐를 골라 원소를 추출(pop)하고, 추출된 원소를 다른 큐에 집어넣는(insert) 작업을 통해 각 큐의 원소 합이 같도록 만들려고 합니다. 이때 필요한 작업의 최소 횟수를 구하고자 합니다. 한 번의 pop과 한 번의 insert를 합쳐서 작업을 1회 수행한 것으로 간주합니다.

큐는 먼저 집어넣은 원소가 먼저 나오는 구조입니다. 이 문제에서는 큐를 배열로 표현하며, 원소가 배열 앞쪽에 있을수록 먼저 집어넣은 원소임을 의미합니다. 즉, pop을 하면 배열의 첫 번째 원소가 추출되며, insert를 하면 배열의 끝에 원소가 추가됩니다. 예를 들어 큐 [1, 2, 3, 4]가 주어졌을 때, pop을 하면 맨 앞에 있는 원소 1이 추출되어 [2, 3, 4]가 되며, 이어서 5를 insert하면 [2, 3, 4, 5]가 됩니다.

다음은 두 큐를 나타내는 예시입니다.

queue1 = [3, 2, 7, 2]
queue2 = [4, 6, 5, 1]

두 큐에 담긴 모든 원소의 합은 30입니다. 따라서, 각 큐의 합을 15로 만들어야 합니다. 예를 들어, 다음과 같이 2가지 방법이 있습니다.

queue2의 4, 6, 5를 순서대로 추출하여 queue1에 추가한 뒤, queue1의 3, 2, 7, 2를 순서대로 추출하여 queue2에 추가합니다. 그 결과 queue1은 [4, 6, 5], queue2는 [1, 3, 2, 7, 2]가 되며, 각 큐의 원소 합은 15로 같습니다. 이 방법은 작업을 7번 수행합니다. queue1에서 3을 추출하여 queue2에 추가합니다. 그리고 queue2에서 4를 추출하여 queue1에 추가합니다. 그 결과 queue1은 [2, 7, 2, 4], queue2는 [6, 5, 1, 3]가 되며, 각 큐의 원소 합은 15로 같습니다. 이 방법은 작업을 2번만 수행하며, 이보다 적은 횟수로 목표를 달성할 수 없습니다. 따라서 각 큐의 원소 합을 같게 만들기 위해 필요한 작업의 최소 횟수는 2입니다.

길이가 같은 두 개의 큐를 나타내는 정수 배열 queue1, queue2가 매개변수로 주어집니다. 각 큐의 원소 합을 같게 만들기 위해 필요한 작업의 최소 횟수를 return 하도록 solution 함수를 완성해주세요. 단, 어떤 방법으로도 각 큐의 원소 합을 같게 만들 수 없는 경우, -1을 return 해주세요.

제한사항 1 ≤ queue1의 길이 = queue2의 길이 ≤ 300,000 1 ≤ queue1의 원소, queue2의 원소 ≤ 109 주의: 언어에 따라 합 계산 과정 중 산술 오버플로우 발생 가능성이 있으므로 long type 고려가 필요합니다.

코드

#include <bits/stdc++.h>
using namespace std;

int solution(vector<int> queue1, vector<int> queue2) {
    int answer = 0, max_ans = queue1.size() * 3;
    long long total = 0, sum1 = 0, sum2 = 0;
    queue<int> q1, q2;
    for(int i = 0; i < queue1.size(); i++){
        total += queue1[i];
        total += queue2[i];
        sum1 += queue1[i];
        sum2 += queue2[i];
        q1.push(queue1[i]);
        q2.push(queue2[i]);
    }
    if(total % 2 == 1) return -1;

    while(1) {
        if(sum1 == sum2) return answer;
        if(sum1 > sum2) {          
            sum1 -= q1.front(); sum2 += q1.front();
            q2.push(q1.front()); q1.pop();
        }
        else {
            sum2 -= q2.front(); sum1 += q2.front();
            q1.push(q2.front()); q2.pop();
        }
        if(answer > max_ans) return -1;
        ++answer;
    }
    return answer;
}

문제가 문제인지라 큐로 푸는게 편할 것 같아 큐를 이용했다.

시소 짝꿍

문제 설명 어느 공원 놀이터에는 시소가 하나 설치되어 있습니다. 이 시소는 중심으로부터 2(m), 3(m), 4(m) 거리의 지점에 좌석이 하나씩 있습니다. 이 시소를 두 명이 마주 보고 탄다고 할 때, 시소가 평형인 상태에서 각각에 의해 시소에 걸리는 토크의 크기가 서로 상쇄되어 완전한 균형을 이룰 수 있다면 그 두 사람을 시소 짝꿍이라고 합니다. 즉, 탑승한 사람의 무게와 시소 축과 좌석 간의 거리의 곱이 양쪽 다 같다면 시소 짝꿍이라고 할 수 있습니다. 사람들의 몸무게 목록 weights이 주어질 때, 시소 짝꿍이 몇 쌍 존재하는지 구하여 return 하도록 solution 함수를 완성해주세요.

제한 사항

• 2 ≤ weights의 길이 ≤ 100,000
• 100 ≤ weights[i] ≤ 1,000
  • 몸무게 단위는 N(뉴턴)으로 주어집니다.
  • 몸무게는 모두 정수입니다.

코드

이중 for문

#include <bits/stdc++.h>
using namespace std;

long long solution(vector<int> weights) {
    sort(weights.begin(), weights.end());
    long long answer = 0;

    for(int i = 0; i < weights.size() - 1; i++){
        for(int j = i + 1; j < weights.size(); j++){ 
            if(weights[i] * 4 < weights[j]) break;
            if(weights[i] == weights[j] || weights[i] * 3 == weights[j] * 2 || 
               weights[i] * 4 == weights[j] * 2 || weights[i] * 4 == weights[j] * 3) ++answer;
        }
    }

    return answer;
}

백준이었으면 시간 초과 났을 것 같은데..? 싶어서 배열을 이용하는 방법으로도 풀어보았다. 실제로 위의 코드는 최대 8000ms의 시간이 걸렸지만, 배열을 이용한 코드에서는 최대 0.41ms밖에 걸리지 않았다.

배열 이용

#include <bits/stdc++.h>
using namespace std;

long long solution(vector<int> weights) {
    long long answer = 0;
    vector<long long> arr(1001, 0);
    for(int i : weights) ++arr[i];

    for(int i = 100; i <= 1000; i++){ 
        if(!arr[i]) continue;
        if(arr[i] > 1) answer += arr[i] * (arr[i] - 1) / 2;
        if(i * 2 <= 1000 && arr[i * 2]) answer += arr[i] * arr[i * 2];
        if(i * 3 / 2 <= 1000 && (i * 3) % 2 == 0 && arr[i * 3 / 2]) answer += arr[i] * arr[i * 3 / 2];
        if(i * 4 / 3 <= 1000 && (i * 4) % 3 == 0 && arr[i * 4 / 3]) answer += arr[i] * arr[i * 4 / 3];
    }

    return answer;
}

오늘의 문제 호텔 대실 무인도 여행 뒤에 있는 큰 수 찾기

호텔 대실

문제 설명 호텔을 운영 중인 코니는 최소한의 객실만을 사용하여 예약 손님들을 받으려고 합니다. 한 번 사용한 객실은 퇴실 시간을 기준으로 10분간 청소를 하고 다음 손님들이 사용할 수 있습니다. 예약 시각이 문자열 형태로 담긴 2차원 배열 book_time이 매개변수로 주어질 때, 코니에게 필요한 최소 객실의 수를 return 하는 solution 함수를 완성해주세요.

제한사항

• 1 ≤ book_time의 길이 ≤ 1,000
  • book_time[i]는 ["HH:MM", "HH:MM"]의 형태로 이루어진 배열입니다
    • [대실 시작 시각, 대실 종료 시각] 형태입니다.
  • 시각은 HH:MM 형태로 24시간 표기법을 따르며, "00:00" 부터 "23:59" 까지로 주어집니다.
    • 예약 시각이 자정을 넘어가는 경우는 없습니다.
    • 시작 시각은 항상 종료 시각보다 빠릅니다.

코드

#include <bits/stdc++.h>
using namespace std;

bool cmp (vector<string> t1, vector<string> t2) {
    if(t1[1].substr(0, 2) == t2[1].substr(0, 2)) {
        return t1[1].substr(3) < t2[1].substr(3); 
    }
    return t1[1].substr(0, 2) < t2[1].substr(0, 2);
}

bool same(vector<string> t1, vector<string> t2) {
    int fh = stoi(t1[1].substr(0, 2));
    int fm = stoi(t1[1].substr(3)) + 10;
    if(fm >= 60) {
        fm -= 60; fh += 1;
    }
    int ih = stoi(t2[0].substr(0, 2));
    int im = stoi(t2[0].substr(3));

    if(fh < ih) return true;
    else if(fh == ih) return fm <= im;
    else return false;
}

int solution(vector<vector<string>> book_time) {
    sort(book_time.begin(), book_time.end(), cmp);

    vector<vector<string>> room;
    room.emplace_back(book_time[0]);
    for(int i = 1; i < book_time.size(); i++){
        for(int j = room.size() - 1; j >= 0 ; j--) {
            if(same(room[j], book_time[i])) {
                room.erase(room.begin() + j);
                break;
            }
        }
        room.emplace_back(book_time[i]);
    }
    return room.size();
}

시간을 다 int형으로 나타내서 priority_queue를 쓸 걸!!

무인도 여행

문제 설명 메리는 여름을 맞아 무인도로 여행을 가기 위해 지도를 보고 있습니다. 지도에는 바다와 무인도들에 대한 정보가 표시돼 있습니다. 지도는 1 x 1크기의 사각형들로 이루어진 직사각형 격자 형태이며, 격자의 각 칸에는 'X' 또는 1에서 9 사이의 자연수가 적혀있습니다. 지도의 'X'는 바다를 나타내며, 숫자는 무인도를 나타냅니다. 이때, 상, 하, 좌, 우로 연결되는 땅들은 하나의 무인도를 이룹니다. 지도의 각 칸에 적힌 숫자는 식량을 나타내는데, 상, 하, 좌, 우로 연결되는 칸에 적힌 숫자를 모두 합한 값은 해당 무인도에서 최대 며칠동안 머물 수 있는지를 나타냅니다. 어떤 섬으로 놀러 갈지 못 정한 메리는 우선 각 섬에서 최대 며칠씩 머물 수 있는지 알아본 후 놀러갈 섬을 결정하려 합니다.

지도를 나타내는 문자열 배열 maps가 매개변수로 주어질 때, 각 섬에서 최대 며칠씩 머무를 수 있는지 배열에 오름차순으로 담아 return 하는 solution 함수를 완성해주세요. 만약 지낼 수 있는 무인도가 없다면 -1을 배열에 담아 return 해주세요.

제한사항

• 3 ≤ maps의 길이 ≤ 100
  • 3 ≤ maps[i]의 길이 ≤ 100
  • maps[i]는 'X' 또는 1 과 9 사이의 자연수로 이루어진 문자열입니다.
  • 지도는 직사각형 형태입니다.

코드

#include <bits/stdc++.h>
using namespace std;

int n, m;
int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};
vector<vector<int>> vis;
vector<string> _maps;

int bfs(int x, int y) {
    queue<pair<int, int>> q;
    q.push({x, y});
    int sz = _maps[x][y] - '0';
    vis[x][y] = 1;

    while(!q.empty()) {
        x = q.front().first;
        y = q.front().second;
        q.pop();

        for(int i = 0; i < 4; i++){
            int nx = x + dx[i];
            int ny = y + dy[i];

            if(nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
            if(vis[nx][ny] || _maps[nx][ny] == 'X') continue;

            q.push({nx, ny});
            sz += _maps[nx][ny] - '0';
            vis[nx][ny] = 1;
        }
    }
    return sz;
}

vector<int> solution(vector<string> maps) {
    n = maps.size(); m = maps[0].size(); _maps = maps;
    vis = vector<vector<int>>(n, vector<int>(m, 0));
    vector<int> answer;

    for(int i = 0; i < n; i++){ 
        for(int j = 0; j < m; j++){
            if(!vis[i][j] && maps[i][j] != 'X') {
                answer.emplace_back(bfs(i, j));
            }
        }
    }
    if(answer.empty()) return {-1};
    sort(answer.begin(), answer.end());
    return answer;
}

평범한 bfs 문제였다

뒤에 있는 큰 수 찾기

문제 설명 정수로 이루어진 배열 numbers가 있습니다. 배열 의 각 원소들에 대해 자신보다 뒤에 있는 숫자 중에서 자신보다 크면서 가장 가까이 있는 수를 뒷 큰수라고 합니다. 정수 배열 numbers가 매개변수로 주어질 때, 모든 원소에 대한 뒷 큰수들을 차례로 담은 배열을 return 하도록 solution 함수를 완성해주세요. 단, 뒷 큰수가 존재하지 않는 원소는 -1을 담습니다.

제한사항

• 4 ≤ numbers의 길이 ≤ 1,000,000
  • 1 ≤ numbers[i]≤ 1,000,000

코드

테스트 21, 22에서 시간 초과

#include <bits/stdc++.h>
using namespace std;

vector<int> solution(vector<int> numbers) {
    vector<int> answer(numbers.size(), -1);
    for(int i = numbers.size() - 2; i >= 0; i--) {
        if(numbers[i] < numbers[i + 1]) answer[i] = numbers[i + 1];
        else if(numbers[i] == numbers[i + 1]) answer[i] = answer[i + 1];
        else {
            if(numbers[i] >= answer[i + 1]) {
                for(int j = i + 1; j < numbers.size(); j++){
                    if(numbers[i] < numbers[j]) {
                        answer[i] = numbers[j];
                        break;
                    }
                }
            }
            else answer[i] = answer[i + 1];
        }
    }
    return answer;
}

시간 초과일 것 같다고 생각했다.. 이 코드에서는 else 문에 들어갔을 때, numbers[i]보다 큰 값이 없는 경우 for문을 끝까지 돌기 때문에 중간에 탈출할 수 있는 구문을 만들어줘야겠다고 생각했다.

 else {
    if(numbers[i] >= answer[i + 1]) {
        for(int j = i + 1; j < numbers.size(); j++){
            if(numbers[i] < numbers[j]) {
                answer[i] = numbers[j];
                break;
            }
            if(numbers[i] >= numbers[j] && answer[j] == -1) break;
    }
}

이렇게 했더니 21번은 통과했다. 22번은 도대체 뭐지?!

잠깐 생각해본 결과 [5, 4, 1, 2, 3, 4, 5, 6] 이런 식으로 들어있으면 시간 초과가 발생할거라는 것을 알아냈다. 그래서 stack을 이용하기로 했다.

성공

#include <bits/stdc++.h>
using namespace std;

vector<int> solution(vector<int> numbers) {
    vector<int> answer(numbers.size(), -1);
    stack<int> st;
    for(int i = numbers.size() - 2; i >= 0; i--) {

        if(numbers[i] < numbers[i + 1]) {
            answer[i] = numbers[i + 1];
            st.push(numbers[i + 1]);
        }
        else if(numbers[i] == numbers[i + 1]) answer[i] = answer[i + 1];
        else {
            if(numbers[i] < answer[i + 1]) answer[i] = answer[i + 1];
            else {
                while(!st.empty()) {
                    if(numbers[i] < st.top()) {
                        answer[i] = st.top();
                        st.push(answer[i]);
                        break;
                    }
                    st.pop();
                }
            }
        }
    }
    return answer;
}

오늘의 문제 혼자서 하는 틱택토 미로 탈출 이모티콘 할인행사 택배 배달과 수거하기

혼자서 하는 틱택토

문제 설명 틱택토는 두 사람이 하는 게임으로 처음에 3x3의 빈칸으로 이루어진 게임판에 선공이 "O", 후공이 "X"를 번갈아가면서 빈칸에 표시하는 게임입니다. 가로, 세로, 대각선으로 3개가 같은 표시가 만들어지면 같은 표시를 만든 사람이 승리하고 게임이 종료되며 9칸이 모두 차서 더 이상 표시를 할 수 없는 경우에는 무승부로 게임이 종료됩니다.

할 일이 없어 한가한 머쓱이는 두 사람이 하는 게임인 틱택토를 다음과 같이 혼자서 하려고 합니다.

• 혼자서 선공과 후공을 둘 다 맡는다.
• 틱택토 게임을 시작한 후 "O"와 "X"를 혼자서 번갈아 가면서 표시를 하면서 진행한다.

틱택토는 단순한 규칙으로 게임이 금방 끝나기에 머쓱이는 한 게임이 종료되면 다시 3x3 빈칸을 그린 뒤 다시 게임을 반복했습니다. 그렇게 틱택토 수 십 판을 했더니 머쓱이는 게임 도중에 다음과 같이 규칙을 어기는 실수를 했을 수도 있습니다.

• "O"를 표시할 차례인데 "X"를 표시하거나 반대로 "X"를 표시할 차례인데 "O"를 표시한다.
• 선공이나 후공이 승리해서 게임이 종료되었음에도 그 게임을 진행한다.

게임 도중 게임판을 본 어느 순간 머쓱이는 본인이 실수를 했는지 의문이 생겼습니다. 혼자서 틱택토를 했기에 게임하는 과정을 지켜본 사람이 없어 이를 알 수는 없습니다. 그러나 게임판만 봤을 때 실제로 틱택토 규칙을 지켜서 진행했을 때 나올 수 있는 상황인지는 판단할 수 있을 것 같고 문제가 없다면 게임을 이어서 하려고 합니다.

머쓱이가 혼자서 게임을 진행하다 의문이 생긴 틱택토 게임판의 정보를 담고 있는 문자열 배열 board가 매개변수로 주어질 때, 이 게임판이 규칙을 지켜서 틱택토를 진행했을 때 나올 수 있는 게임 상황이면 1을 아니라면 0을 return 하는 solution 함수를 작성해 주세요.

제한사항

• board의 길이 = board[i]의 길이 = 3
  • board의 원소는 모두 "O", "X", "."으로만 이루어져 있습니다.
• board[i][j]는 i + 1행 j + 1열에 해당하는 칸의 상태를 나타냅니다.
  • "."은 빈칸을, "O"와 "X"는 해당 문자로 칸이 표시되어 있다는 의미입니다.

코드

#include <bits/stdc++.h>
using namespace std;

int solution(vector<string> board) {
    int onum = 0, xnum = 0;
    for(string s : board){
        for(char c : s){
            if(c == 'O') onum++;
            else if(c == 'X') xnum++;
        }
    }
    if(onum < xnum || onum - xnum > 1) return 0;

    bool owin = false, xwin = false;
    for(int i = 0; i < 3; i++){
        if(board[i][0] != '.' && board[i][0] == board[i][1] && board[i][0] == board[i][2]) {
            if(board[i][0] == 'O') owin = true;
            else xwin = true;
        }
        if(board[0][i] != '.' && board[0][i] == board[1][i] && board[0][i] == board[2][i]) {
            if(board[0][i] == 'O') owin = true;
            else xwin = true;
        }
    }
    if(board[0][0] != '.' && board[0][0] == board[1][1] && board[0][0] == board[2][2]){
        if(board[0][0] == 'O') owin = true;
        else xwin = true;
    }
    if(board[2][0] != '.' && board[2][0] == board[1][1] && board[2][0] == board[0][2])  {
        if(board[2][0] == 'O') owin = true;
        else xwin = true;
    }

    if(owin){
        if(xwin) return 0;
        else if(onum <= xnum) return 0;
    }
    else if(xwin && onum != xnum) return 0;
    return 1;
}

3x3의 작은 배열이므로 그냥 모든 경우의 수를 구해서 풀어도 된다.

미로 탈출

문제 설명 1 x 1 크기의 칸들로 이루어진 직사각형 격자 형태의 미로에서 탈출하려고 합니다. 각 칸은 통로 또는 벽으로 구성되어 있으며, 벽으로 된 칸은 지나갈 수 없고 통로로 된 칸으로만 이동할 수 있습니다. 통로들 중 한 칸에는 미로를 빠져나가는 문이 있는데, 이 문은 레버를 당겨서만 열 수 있습니다. 레버 또한 통로들 중 한 칸에 있습니다. 따라서, 출발 지점에서 먼저 레버가 있는 칸으로 이동하여 레버를 당긴 후 미로를 빠져나가는 문이 있는 칸으로 이동하면 됩니다. 이때 아직 레버를 당기지 않았더라도 출구가 있는 칸을 지나갈 수 있습니다. 미로에서 한 칸을 이동하는데 1초가 걸린다고 할 때, 최대한 빠르게 미로를 빠져나가는데 걸리는 시간을 구하려 합니다.

미로를 나타낸 문자열 배열 maps가 매개변수로 주어질 때, 미로를 탈출하는데 필요한 최소 시간을 return 하는 solution 함수를 완성해주세요. 만약, 탈출할 수 없다면 -1을 return 해주세요.

제한사항

• 5 ≤ maps의 길이 ≤ 100
  • 5 ≤ maps[i]의 길이 ≤ 100
  • maps[i]는 다음 5개의 문자들로만 이루어져 있습니다.
    • S : 시작 지점
    • E : 출구
    • L : 레버
    • O : 통로
    • X : 벽
  • 시작 지점과 출구, 레버는 항상 다른 곳에 존재하며 한 개씩만 존재합니다.
  • 출구는 레버가 당겨지지 않아도 지나갈 수 있으며, 모든 통로, 출구, 레버, 시작점은 여러 번 지나갈 수 있습니다.

코드

#include <bits/stdc++.h>
using namespace std;

vector<string> _maps;
int n, m, sx, sy, lx, ly, ex, ey;
int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};

int bfs(int x, int y, int fx, int fy) {
    queue<pair<int, int>> q;
    vector<vector<int>> dis(n, vector<int>(m, -1));
    q.push({x, y});
    dis[x][y] = 0;

    while(!q.empty()){
        x = q.front().first;
        y = q.front().second;
        q.pop();

        if(x == fx && y == fy) return dis[x][y];
        for(int i = 0; i < 4; i++){
            int nx = x + dx[i];
            int ny = y + dy[i];

            if(nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
            if(dis[nx][ny] != -1 || _maps[nx][ny] == 'X') continue;
            q.push({nx, ny});
            dis[nx][ny] = dis[x][y] + 1;
        }
    }
    return -1;
}

int solution(vector<string> maps) {
    _maps = maps;
    n = maps.size(); m = maps[0].size();
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            if(maps[i][j] == 'S') {
                sx = i; sy = j;
            }
            else if(maps[i][j] == 'E') {
                ex = i; ey = j;
            }
            else if(maps[i][j] == 'L') {
                lx = i; ly = j;
            }
        }
    }
    int move1 = bfs(sx, sy, lx, ly);
    int move2 = bfs(lx, ly, ex, ey);
    if(move1 == -1 || move2 == -1) return -1;
    return move1 + move2;
}

S에서 L까지의 최단 거리 + L에서 E까지의 최단 거리를 구하면 된다.

이모티콘 할인행사

문제 설명 카카오톡에서는 이모티콘을 무제한으로 사용할 수 있는 이모티콘 플러스 서비스 가입자 수를 늘리려고 합니다. 이를 위해 카카오톡에서는 이모티콘 할인 행사를 하는데, 목표는 다음과 같습니다.

1. 이모티콘 플러스 서비스 가입자를 최대한 늘리는 것.
2. 이모티콘 판매액을 최대한 늘리는 것.

1번 목표가 우선이며, 2번 목표가 그 다음입니다.

이모티콘 할인 행사는 다음과 같은 방식으로 진행됩니다.

• n명의 카카오톡 사용자들에게 이모티콘 m개를 할인하여 판매합니다.

• 이모티콘마다 할인율은 다를 수 있으며, 할인율은 10%, 20%, 30%, 40% 중 하나로 설정됩니다. 카카오톡 사용자들은 다음과 같은 기준을 따라 이모티콘을 사거나, 이모티콘 플러스 서비스에 가입합니다.

• 각 사용자들은 자신의 기준에 따라 일정 비율 이상 할인하는 이모티콘을 모두 구매합니다.

• 각 사용자들은 자신의 기준에 따라 이모티콘 구매 비용의 합이 일정 가격 이상이 된다면, 이모티콘 구매를 모두 취소하고 이모티콘 플러스 서비스에 가입합니다.

다음은 2명의 카카오톡 사용자와 2개의 이모티콘이 있을때의 예시입니다.

1번 사용자는 40%이상 할인하는 이모티콘을 모두 구매하고, 이모티콘 구매 비용이 10,000원 이상이 되면 이모티콘 구매를 모두 취소하고 이모티콘 플러스 서비스에 가입합니다. 2번 사용자는 25%이상 할인하는 이모티콘을 모두 구매하고, 이모티콘 구매 비용이 10,000원 이상이 되면 이모티콘 구매를 모두 취소하고 이모티콘 플러스 서비스에 가입합니다.

1번 이모티콘의 가격은 7,000원, 2번 이모티콘의 가격은 9,000원입니다.

만약, 2개의 이모티콘을 모두 40%씩 할인한다면, 1번 사용자와 2번 사용자 모두 1,2번 이모티콘을 구매하게 되고, 결과는 다음과 같습니다.

이모티콘 플러스 서비스 가입자는 0명이 늘어나고 이모티콘 판매액은 19,200원이 늘어납니다.

하지만, 1번 이모티콘을 30% 할인하고 2번 이모티콘을 40% 할인한다면 결과는 다음과 같습니다.

2번 사용자는 이모티콘 구매 비용을 10,000원 이상 사용하여 이모티콘 구매를 모두 취소하고 이모티콘 플러스 서비스에 가입하게 됩니다. 따라서, 이모티콘 플러스 서비스 가입자는 1명이 늘어나고 이모티콘 판매액은 5,400원이 늘어나게 됩니다.

카카오톡 사용자 n명의 구매 기준을 담은 2차원 정수 배열 users, 이모티콘 m개의 정가를 담은 1차원 정수 배열 emoticons가 주어집니다. 이때, 행사 목적을 최대한으로 달성했을 때의 이모티콘 플러스 서비스 가입 수와 이모티콘 매출액을 1차원 정수 배열에 담아 return 하도록 solution 함수를 완성해주세요.

제한사항

• 1 ≤ users의 길이 = n ≤ 100
  • users의 원소는 [비율, 가격]의 형태입니다.
  • users[i]는 i+1번 고객의 구매 기준을 의미합니다.
  • 비율% 이상의 할인이 있는 이모티콘을 모두 구매한다는 의미입니다.
    • 1 ≤ 비율 ≤ 40
  • 가격이상의 돈을 이모티콘 구매에 사용한다면, 이모티콘 구매를 모두 취소하고 이모티콘 플러스 서비스에 가입한다는 의미입니다.
    • 100 ≤ 가격 ≤ 1,000,000
    • 가격은 100의 배수입니다.
• 1 ≤ emoticons의 길이 = m ≤ 7
  • emoticons[i]는 i+1번 이모티콘의 정가를 의미합니다.
  • 100 ≤ emoticons의 원소 ≤ 1,000,000
  • emoticons의 원소는 100의 배수입니다.

코드

#include <bits/stdc++.h>
using namespace std;

int n, eplus, price;
vector<int> sale, _emoticons;
vector<vector<int>> _users;
int pc[4] = {10, 20, 30, 40};

void buy(int k) {
    if(k == n) {
        int cnt = 0, emo = 0;
        for(vector<int> v : _users) {
            int now = 0;
            for(int i = 0; i < n; i++){
                if(sale[i] >= v[0]) now += (_emoticons[i] * (100 - sale[i]) / 100);
            }
            if(now >= v[1]) ++cnt;
            else emo += now;
        }
        if(eplus < cnt) {
            eplus = cnt; price = emo;
        }
        else if(eplus == cnt) price = max(price, emo);
        return;
    }
    for(int i = 0; i < 4; i++){
        sale[k] = pc[i];
        buy(k + 1);
    }

}

vector<int> solution(vector<vector<int>> users, vector<int> emoticons) {
    n = emoticons.size();
    _users = users; _emoticons = emoticons;
    sale = vector<int>(n, 0);
    buy(0);

    return {eplus, price};
}

이모티콘의 할인률이 4가지, 이모티콘 개수가 7개이므로 모든 이모티콘의 모든 할인률을 계산해서 최댓값을 구해도 4*7가지밖에 없기 때문에 연산량이 그다지 많지 않다.

택배 배달과 수거하기

문제 설명

당신은 일렬로 나열된 n개의 집에 택배를 배달하려 합니다. 배달할 물건은 모두 크기가 같은 재활용 택배 상자에 담아 배달하며, 배달을 다니면서 빈 재활용 택배 상자들을 수거하려 합니다. 배달할 택배들은 모두 재활용 택배 상자에 담겨서 물류창고에 보관되어 있고, i번째 집은 물류창고에서 거리 i만큼 떨어져 있습니다. 또한 i번째 집은 j번째 집과 거리 j - i만큼 떨어져 있습니다. (1 ≤ i ≤ j ≤ n) 트럭에는 재활용 택배 상자를 최대 cap개 실을 수 있습니다. 트럭은 배달할 재활용 택배 상자들을 실어 물류창고에서 출발해 각 집에 배달하면서, 빈 재활용 택배 상자들을 수거해 물류창고에 내립니다. 각 집마다 배달할 재활용 택배 상자의 개수와 수거할 빈 재활용 택배 상자의 개수를 알고 있을 때, 트럭 하나로 모든 배달과 수거를 마치고 물류창고까지 돌아올 수 있는 최소 이동 거리를 구하려 합니다. 각 집에 배달 및 수거할 때, 원하는 개수만큼 택배를 배달 및 수거할 수 있습니다.

다음은 cap=4 일 때, 최소 거리로 이동하면서 5개의 집에 배달 및 수거하는 과정을 나타낸 예시입니다.

배달 및 수거할 재활용 택배 상자 개수

배달 및 수거 과정

16(=5+5+3+3)의 거리를 이동하면서 모든 배달 및 수거를 마쳤습니다. 같은 거리로 모든 배달 및 수거를 마치는 다른 방법이 있지만, 이보다 짧은 거리로 모든 배달 및 수거를 마치는 방법은 없습니다.

트럭에 실을 수 있는 재활용 택배 상자의 최대 개수를 나타내는 정수 cap, 배달할 집의 개수를 나타내는 정수 n, 각 집에 배달할 재활용 택배 상자의 개수를 담은 1차원 정수 배열 deliveries와 각 집에서 수거할 빈 재활용 택배 상자의 개수를 담은 1차원 정수 배열 pickups가 매개변수로 주어집니다. 이때, 트럭 하나로 모든 배달과 수거를 마치고 물류창고까지 돌아올 수 있는 최소 이동 거리를 return 하도록 solution 함수를 완성해 주세요.

제한사항

• 1 ≤ cap ≤ 50
• 1 ≤ n ≤ 100,000
• deliveries의 길이 = pickups의 길이 = n
  • deliveries[i]는 i+1번째 집에 배달할 재활용 택배 상자의 개수를 나타냅니다.
  • pickups[i]는 i+1번째 집에서 수거할 빈 재활용 택배 상자의 개수를 나타냅니다.
  • 0 ≤ deliveries의 원소 ≤ 50
  • 0 ≤ pickups의 원소 ≤ 50
• 트럭의 초기 위치는 물류창고입니다.

코드

테스트 16, 17 시간 초과

#include <bits/stdc++.h>
using namespace std;

long long solution(int cap, int n, vector<int> deliveries, vector<int> pickups) {
    long long answer = 0;
    int idx = n - 1, del = 0, pic = 0;
    while(1) {
        int now = 0, box = 0, dis = 0;
        for(int i = n - 1; i >= 0; i--) {
            if(now == cap && box == cap) break;
            if(deliveries[i] > 0 && now < cap) {
                dis = max(dis, i + 1);
                del = i;
                if(deliveries[i] + now <= cap) {
                    now += deliveries[i];
                    deliveries[i] = 0;
                }
                else {
                    deliveries[i] -= (cap - now);
                    now = cap;
                }
            }
            if(pickups[i] > 0 && box < cap) {
                dis = max(dis, i + 1);
                pic = i;
                if(pickups[i] + box <= cap) {
                    box += pickups[i];
                    pickups[i] = 0;
                }
                else {
                    pickups[i] -= (cap - box);
                    box = cap;
                }
            }
        }
        idx = max(del, pic);
        if(dis == 0) break;
        else answer += (dis * 2);
    }
    return answer;
}

n번째 집(idx : n-1)부터 시작하며 배달과 수거를 했다. 아무래도 계속 i = n-1부터 시작하므로 비효율적인 것 같았다.

성공

#include <bits/stdc++.h>
using namespace std;

long long solution(int cap, int n, vector<int> deliveries, vector<int> pickups) {
    long long answer = 0, delnum = 0, picnum = 0;
    for(int i = 0; i < n; i++){
        delnum += deliveries[i];
        picnum += pickups[i];
    }
    while(1) {
        int now = 0, box = 0, dis = 0;
        for(int i = idx; i >= 0; i--) {
            if((now == cap || delnum <= 0) && (box == cap || picnum <= 0)) break;
            if(deliveries[i] > 0 && now < cap) {
                dis = max(dis, i + 1);
                if(deliveries[i] + now <= cap) {
                    now += deliveries[i];
                    deliveries[i] = 0;
                }
                else {
                    deliveries[i] -= (cap - now);
                    now = cap;
                }
            }
            if(pickups[i] > 0 && box < cap) {
                dis = max(dis, i + 1);
                if(pickups[i] + box <= cap) {
                    box += pickups[i];
                    pickups[i] = 0;
                }
                else {
                    pickups[i] -= (cap - box);
                    box = cap;
                }
            }
        }
        idx = max(del, pic);
        if(dis == 0) break;
        else answer += (dis * 2);
        delnum -= cap; picnum -= cap;
    }
    return answer;
}

처음에는 idx 변수를 이용해 시작하는 집만 변경하게 했다. 배달과 수거 중 해야하는 일이 남은(?) 집의 인덱스가 더 큰 곳을 저장하게 해서 해당 인덱스부터 다시 시작하게 했으나.. 17번에서 또 시간초과.

작성한 코드에서는 now(배달한 상자 수)와 box(수거한 상자 수)가 cap이 되어야만 for문에서 탈출하므로, 둘 중 하나의 작업이 모두 끝난 상태에서 다른 작업을 하는 경우 i = 0이 될 때까지 for문을 탈출할 수 없다. 이것 때문에 시간 초과가 발생하는 것으로 판단해서 남은 배달 수, 남은 수거 수를 나타내는 변수를 만들어 관리했다.

오늘의 문제 [PCCP 기출문제] 2번 / 석유 시추 리코쳇 로봇 당구 연습

[PCCP 기출문제] 2번 / 석유 시추

문제 설명 [본 문제는 정확성과 효율성 테스트 각각 점수가 있는 문제입니다.]

세로길이가 n 가로길이가 m인 격자 모양의 땅 속에서 석유가 발견되었습니다. 석유는 여러 덩어리로 나누어 묻혀있습니다. 당신이 시추관을 수직으로 단 하나만 뚫을 수 있을 때, 가장 많은 석유를 뽑을 수 있는 시추관의 위치를 찾으려고 합니다. 시추관은 열 하나를 관통하는 형태여야 하며, 열과 열 사이에 시추관을 뚫을 수 없습니다.

예를 들어 가로가 8, 세로가 5인 격자 모양의 땅 속에 위 그림처럼 석유가 발견되었다고 가정하겠습니다. 상, 하, 좌, 우로 연결된 석유는 하나의 덩어리이며, 석유 덩어리의 크기는 덩어리에 포함된 칸의 수입니다. 그림에서 석유 덩어리의 크기는 왼쪽부터 8, 7, 2입니다.

시추관은 위 그림처럼 설치한 위치 아래로 끝까지 뻗어나갑니다. 만약 시추관이 석유 덩어리의 일부를 지나면 해당 덩어리에 속한 모든 석유를 뽑을 수 있습니다. 시추관이 뽑을 수 있는 석유량은 시추관이 지나는 석유 덩어리들의 크기를 모두 합한 값입니다. 시추관을 설치한 위치에 따라 뽑을 수 있는 석유량은 다음과 같습니다.

석유가 묻힌 땅과 석유 덩어리를 나타내는 2차원 정수 배열 land가 매개변수로 주어집니다. 이때 시추관 하나를 설치해 뽑을 수 있는 가장 많은 석유량을 return 하도록 solution 함수를 완성해 주세요.

제한사항

• 1 ≤ land의 길이 = 땅의 세로길이 = n ≤ 500
  • 1 ≤ land[i]의 길이 = 땅의 가로길이 = m ≤ 500
  • land[i][j]는 i+1행 j+1열 땅의 정보를 나타냅니다.
  • land[i][j]는 0 또는 1입니다.
  • land[i][j]가 0이면 빈 땅을, 1이면 석유가 있는 땅을 의미합니다.

정확성 테스트 케이스 제한사항

• 1 ≤ land의 길이 = 땅의 세로길이 = n ≤ 100
  • 1 ≤ land[i]의 길이 = 땅의 가로길이 = m ≤ 100

효율성 테스트 케이스 제한사항

• 주어진 조건 외 추가 제한사항 없습니다.

코드

#include <bits/stdc++.h>
using namespace std;

int n, m, max_oil;
vector<vector<int>>  _land;
map<int, int> land_size;
int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};

int bfs(int x, int y, int k){
    queue<pair<int, int>> q;
    q.push({x, y});
    _land[x][y] = k;
    int sz = 1;

    while(!q.empty()){
        int nowx = q.front().first;
        int nowy = q.front().second;
        q.pop();

        for(int i = 0; i < 4; i++){
            int nx = nowx + dx[i];
            int ny = nowy + dy[i];

            if(nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
            if( _land[nx][ny] != 1) continue;
            q.push({nx, ny});
            ++sz; _land[nx][ny] = k;
        }
    }
    return sz;
}

void bfs_all(){
    int k = 2;
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            if(_land[i][j] == 1) {
                land_size.insert({k, bfs(i, j, k)});
                ++k;
            }
        }
    }
}


int solution(vector<vector<int>> land) {
    _land = land;
    n = land.size(); m = land[0].size();
    bfs_all();

    for(int i = 0; i < m; i++){
        set<int> t;
        for(int j = 0; j < n; j++){
            if(_land[j][i] != 0) t.insert(_land[j][i]);
        }
        int now = 0;
        for(int ti : t) now += land_size[ti];
        max_oil = max(max_oil, now);
    }

    return max_oil;
}

효율성 테스트로 인해 bfs로 석유에 번호를 매기고, 각 석유 덩어리의 크기 map에 저장했다.

각 열 별로 순회하며 해당 열에 속한 석유의 번호를 set(중복 X)에 저장하고, 해당 석유의 크기를 모두 더해 max 값을 찾았다.

리코쳇 로봇

문제 설명 리코쳇 로봇이라는 보드게임이 있습니다.

이 보드게임은 격자모양 게임판 위에서 말을 움직이는 게임으로, 시작 위치에서 목표 위치까지 최소 몇 번만에 도달할 수 있는지 말하는 게임입니다.

이 게임에서 말의 움직임은 상, 하, 좌, 우 4방향 중 하나를 선택해서 게임판 위의 장애물이나 맨 끝에 부딪힐 때까지 미끄러져 이동하는 것을 한 번의 이동으로 칩니다.

다음은 보드게임판을 나타낸 예시입니다.

...D..R
.D.G...
....D.D
D....D.
..D....

여기서 "."은 빈 공간을, "R"은 로봇의 처음 위치를, "D"는 장애물의 위치를, "G"는 목표지점을 나타냅니다. 위 예시에서는 "R" 위치에서 아래, 왼쪽, 위, 왼쪽, 아래, 오른쪽, 위 순서로 움직이면 7번 만에 "G" 위치에 멈춰 설 수 있으며, 이것이 최소 움직임 중 하나입니다.

게임판의 상태를 나타내는 문자열 배열 board가 주어졌을 때, 말이 목표위치에 도달하는데 최소 몇 번 이동해야 하는지 return 하는 solution함수를 완성하세요. 만약 목표위치에 도달할 수 없다면 -1을 return 해주세요.

제한 사항

• 3 ≤ board의 길이 ≤ 100
  • 3 ≤ board의 원소의 길이 ≤ 100
  • board의 원소의 길이는 모두 동일합니다.
  • 문자열은 ".", "D", "R", "G"로만 구성되어 있으며 각각 빈 공간, 장애물, 로봇의 처음 위치, 목표 지점을 나타냅니다.
  • "R"과 "G"는 한 번씩 등장합니다.

코드

#include <bits/stdc++.h>
using namespace std;

int dx[4] = {0, 1, 0, -1};  // 동 남 서 북
int dy[4] = {1, 0, -1, 0};
int x, y, n, m;
vector<vector<int>> dis;
vector<string> _board;

int move(){
    queue<pair<int, int>> q;
    q.push({x, y});
    dis[x][y] = 0;

    while(!q.empty()){
        x = q.front().first;
        y = q.front().second;
        q.pop();

        if(_board[x][y] == 'G') return dis[x][y];

        for(int i = 0; i < 4; i++){
            int nx = x + dx[i];
            int ny = y + dy[i];

            if(nx < 0 || nx >= n || ny < 0 || ny >= m || _board[nx][ny] == 'D') continue;

            while(1){
                if(nx + dx[i] < 0 || nx + dx[i] >= n || ny + dy[i] < 0 || ny +dy[i] >= m || _board[nx + dx[i]][ny + dy[i]] == 'D') {
                    if(dis[nx][ny] != -1) break;
                    dis[nx][ny] = dis[x][y] + 1;
                    q.push({nx, ny});
                    break;
                }
                nx += dx[i];
                ny += dy[i];
            }
        }
    }
    return -1;
}

int solution(vector<string> board) {
    _board = board;
    n = board.size(); m = board[0].size();
    dis = vector<vector<int>>(n, vector<int>(m, -1));
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            if(board[i][j] == 'R') {
                x = i; y = j;
                break;
            }
        }
    }
    return move();
}

당구 연습

문제 설명 프로그래머스의 마스코트인 머쓱이는 최근 취미로 당구를 치기 시작했습니다.

머쓱이는 손 대신 날개를 사용해야 해서 당구를 잘 못 칩니다. 하지만 끈기가 강한 머쓱이는 열심히 노력해서 당구를 잘 치려고 당구 학원에 다니고 있습니다.

오늘도 당구 학원에 나온 머쓱이에게 당구 선생님이"원쿠션"(당구에서 공을 쳐서 벽에 맞히는 걸 쿠션이라고 부르고, 벽에 한 번 맞힌 후 공에 맞히면 원쿠션이라고 부릅니다) 연습을 하라면서 당구공의 위치가 담긴 리스트를 건네줬습니다. 리스트에는 머쓱이가 맞춰야 하는 공들의 위치가 담겨있습니다. 머쓱이는 리스트에 담긴 각 위치에 순서대로 공을 놓아가며 "원쿠션" 연습을 하면 됩니다. 이때, 머쓱이는 항상 같은 위치에 공을 놓고 쳐서 리스트에 담긴 위치에 놓인 공을 맞춥니다.

머쓱이와 달리 최근 취미로 알고리즘 문제를 풀기 시작한 당신은, 머쓱이가 친 공이 각각의 목표로한 공에 맞을 때까지 최소 얼마의 거리를 굴러가야 하는지가 궁금해졌습니다.

당구대의 가로 길이 m, 세로 길이 n과 머쓱이가 쳐야 하는 공이 놓인 위치 좌표를 나타내는 두 정수 startX, startY, 그리고 매 회마다 목표로 해야하는 공들의 위치 좌표를 나타내는 정수 쌍들이 들어있는 2차원 정수배열 balls가 주어집니다. "원쿠션" 연습을 위해 머쓱이가 공을 적어도 벽에 한 번은 맞춘 후 목표 공에 맞힌다고 할 때, 각 회마다 머쓱이가 친 공이 굴러간 거리의 최솟값의 제곱을 배열에 담아 return 하도록 solution 함수를 완성해 주세요.

단, 머쓱이가 친 공이 벽에 부딪힐 때 진행 방향은 항상 입사각과 반사각이 동일하며, 만약 꼭짓점에 부딪힐 경우 진입 방향의 반대방향으로 공이 진행됩니다. 공의 크기는 무시하며, 두 공의 좌표가 정확히 일치하는 경우에만 두 공이 서로 맞았다고 판단합니다. 공이 목표 공에 맞기 전에 멈추는 경우는 없으며, 목표 공에 맞으면 바로 멈춘다고 가정합니다.

위 그림은 친 공이 벽에 맞았을 때의 움직임을 나타낸 그림입니다. 치기 전 공의 위치가 점 A입니다.

위 그림은 친 공이 꼭짓점에 맞았을 때의 움직임을 나타낸 그림입니다. 치기 전 공의 위치가 점 A입니다.

제한사항

• 3 ≤ m, n ≤ 1,000
• 0 < startX < m
• 0 < startY < n
• 2 ≤ balls의 길이 ≤ 1,000
• balls의 원소는 [a, b] 형태입니다.
  • a, b는 머쓱이가 맞춰야 할 공이 놓인 좌표를 의미합니다.
  • 0 < a < m, 0 < b < n
  • (a, b) = ( startX, startY )인 입력은 들어오지 않습니다.

코드

#include <bits/stdc++.h>
using namespace std;

vector<int> solution(int m, int n, int startX, int startY, vector<vector<int>> balls) {
    vector<int> answer;
    for(vector<int> v : balls){
        int len = 0;
        if(startX == v[0]) {
            if(m - startX < startX) len = pow(2 * (m - startX), 2) + pow(startY - v[1], 2);
            else len = pow(2 * startX, 2) + pow(startY - v[1], 2);
            if(startY < v[1]) len = min(len, (int)(pow(startY + v[1], 2)));
            else len = min(len, (int)pow(2 * n - startY - v[1], 2));
        }
        else if(startY  == v[1]) {
            if(n - startY < startY) len = pow(startX - v[0], 2) + pow(2 * (n - startY), 2);
            else len = pow(startX - v[0], 2) + pow(2 * startY, 2);
            if(startX < v[0]) len = min(len, (int)(pow(startX + v[0], 2)));
            else len = min(len, (int)pow(2 * m - startX - v[0], 2));
        }
        else{
            len = min({pow(2 * m - startX - v[0], 2) + pow(startY - v[1], 2), pow(-startX - v[0], 2) + pow(startY - v[1], 2), pow(startX - v[0], 2) + pow(2 * n - startY - v[1], 2), pow(startX - v[0], 2) + pow(-startY - v[1], 2)});
        }
        answer.emplace_back(len);
    }

    return answer;
}

입사각과 반사각이 같은 최단 거리를 구하는 방법은 시작점을 x = 0, x = n, y = 0, y = m으로 대칭이동한 점과의 거리 중 가장 짧은 거리를 구하면 된다.

그런데! x 좌표나 y 좌표가 같은 경우 목표 좌표 방향으로는 이동할 수 없고(한 번 튕겨야하므로), 반대 방향으로 튕기는 것도 고려해야한다.(이거 안하면 31번 이후 테스트케이스가 터진다)